我实现了一个仅适用于 7 个元素的 QuickSort 算法，然后给出了 8 个或更多元素的 StackOverflow 错误

Question

我实现了一个仅适用于 7 个元素的快速排序算法，然后对 8 个或更多元素给出 Whosebug 错误。进入无限循环。对于数组中存在的元素数量来说工作正常，但如果我再添加一个元素，它 returns 一个 Whosebug 错误这是我的代码：

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;
}
}

Answer 1

我认为问题在于您没有将枢轴放在正确的位置。

这是您的代码，稍作改动：

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;
}

此外，在您的排序方法中，调用 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);
  }
}

我实现了一个仅适用于 7 个元素的 QuickSort 算法，然后给出了 8 个或更多元素的 StackOverflow 错误

I implemented a QuickSort Algorithm which only works for 7 elements and then gives a StackOverflow Error for 8 elements or more

java

arrays

sorting

algorithm

quicksort