英文:
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 index
int 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);
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论