英文:
I implemented a QuickSort Algorithm which only works for 7 elements and then gives a StackOverflow Error for 8 elements or more
问题
我实现了一个快速排序算法，该算法仅适用于7个元素，对于8个或更多的元素会产生堆栈溢出错误，进入无限循环。对于数组中存在的元素数量，它能正常工作，但如果我再添加一个元素，就会返回堆栈溢出错误。以下是我的代码：
public class QuickSort{public void main(){QuickSort o = new QuickSort();int arr[] = {8, 5, 2, 10, 1, 7, 3};o.sort(arr, 0, arr.length - 1);for (int i = 0; i < arr.length; i++)System.out.print(arr[i] + " ");}void sort(int[] arr, int l, int h){if (l < h){int pi = partition(arr, l, h);sort(arr, l, pi);sort(arr, pi + 1, h);}}int partition(int arr[], int l, int h){int pivot = arr[l];int i = l, j = h;while (i < j){while (arr[i] <= pivot){i++;}while (arr[j] > pivot){j--;}if (i < j){int t = arr[i];arr[i] = arr[j];arr[j] = t;}}int t = arr[j];arr[j] = pivot;arr[l] = t;return j;}}
英文:
I implemented a QuickSort Algorithm which only works for 7 elements and then gives a StackOverflow Error for 8 elements or more. Goes into an infinite loop. Works fine for the number of elements that are present in the array but if I add one more element, it returns a StackOverflow Error
Here is my code:
public class QuickSort{public void main(){QuickSort o = new QuickSort();int arr[] = {8,5,2,10,1,7,3};o.sort(arr,0,arr.length-1);for(int i=0;i<arr.length;i++)System.out.print(arr[i]+" ");}void sort(int []arr,int l,int h){if(l<h){int pi = partition(arr,l,h);sort(arr,l,pi);sort(arr,pi+1,h);}}int partition(int arr[],int l,int h){int pivot = arr[l];int i=l,j=h;while(i<j){while(arr[i]<=pivot){i++;}while(arr[j]>pivot){j--;}if(i<j){int t = arr[i];arr[i] = arr[j];arr[j] = t;}}int t = arr[j];arr[j] = pivot;arr[l] = t;return j;}}
答案1
得分: 0
我认为问题在于您没有将枢轴放在正确的位置。
以下是您的代码做了一个小改动后的版本：
int partition(int arr[], int l, int h) {int pivot = arr[l];int i = l, j = h;while (i < j) {while (i < j && arr[i] <= pivot) { i++; }while (i < j && arr[j] > pivot) { j--; }if (i < j) {int t = arr[i];arr[i] = arr[j];arr[j] = t;}}// 这里确定了枢轴应该放置的位置。通过示例最容易理解// 循环后，数组可能是 3 1 2 4 5// 枢轴是 3，应该与数字 2 进行交换，但索引 j 有时指向数字 2，有时指向数字 4// 以下代码确定了所需的索引int lowerInd = arr[j] <= pivot ? j : j - 1;int t = arr[lowerInd];arr[lowerInd] = arr[l];arr[l] = t;return lowerInd;}此外，在您的排序方法中，请调用 `sort(arr, l, pi - 1);`，而不是 `sort(arr, l, pi);`void sort(int[] arr, int l, int h) {if (l < h) {int pi = partition(arr, l, h);sort(arr, l, pi - 1);sort(arr, pi + 1, h);}}
如需进一步帮助，请随时提问。
英文:
I believe the problem is that you don't put the pivot in the right place.
Here is your code with a small change:
int partition(int arr[],int l,int h){int pivot = arr[l];int i= l,j=h;while(i < j){while( i < j && arr[i]<=pivot){ i++;}while( i < j && arr[j]>pivot){ j--;}if(i< j){int t = arr[i];arr[i] = arr[j];arr[j] = t;}}//here it is determined where the pivot should go. It is easiest to understand with an example//after the loop arr can be 3 1 2 4 5//the pivot being 3 should be switched with the number 2 but index j sometimes points to number 2 and sometimes to number 4//the following code determines the desired indexint lowerInd = arr[j] <= pivot ? j : j - 1;int t = arr[lowerInd];arr[lowerInd] = arr[l];arr[l] = t;return lowerInd;}
Also, in your sort method, call sort(arr,l,pi - 1); instead of sort(arr,l,pi);
void sort(int[] arr,int l,int h){if(l<h){int pi = partition(arr,l,h);sort(arr,l,pi - 1);sort(arr,pi+1,h);}}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论