快速排序堆栈溢出错误

Question

在为考试练习时，我遇到了一个（对我来说）奇怪的快速排序问题。

我的实现：

    public void quicksort(int l, int r)
{
    if(l<r && l>0 && r<=array.length-1)
    {
        int pivot = array[pivot(l, r)];
        int i = l;
        int j = r;
        if(j==i+1)
        {
            if(array[i]>array[j])
            {
                System.out.println(array[i]+"<->"+array[j]);
                int help = array[i];      
                array[i] = array[j];  
                array[j] = help;    
            }
        }
        else{ while(i<=j)
            {
                if(array[i]>=pivot && pivot>= array[j])
                {
                    System.out.println(array[i]+">="+pivot+">="+array[j]);

                    int help = array[i];      
                    array[i] = array[j];  
                    array[j] = help;
                    i++;
                    j--;
                }
                else{
                    i++;
                }
            }
            if(l<j && j<array.length-1)quicksort(l, j);
            if(i<r)quicksort(i, r);
        }
    }
}

但这在（此处）第 34 行中给了我一个 "Java.lang.WhosebugError: null"。但是，可以通过在第 34 行和第 35 行中将 j 与 j-1 和 i 与 j 交换来避免此错误。我真的尝试了我想到的一切，但我真的想不出解决方案：/

Answer 1

我认为快速排序有更好的实现，这是我尝试的评论，希望能帮助您更好地记住它：

public static void quickSort(int[] theArray, int left, int right) {
    //we declare 2 variables   
    int i = left;
    int j = right;

    //we calculate a pivot, simply taking the middle value of the array
    int pivot = theArray[(left+right)/2];

    //check that i hasn't gone beyond j (i starts at 0, j starts at array.length)
    while(i<=j){
        //if here, must mean i is less-than or equal to j, so check to see if
        //the array value i is less than our pivot
        while(theArray[i] < pivot){
            //if it is less-than pivot, the value theArray[i] is in correct place
            //so we can increment i to go to next 
            i++;
        }
        //now do exactly same thing for j, however, j starts at array.length, so decrement
        while(theArray[j] > pivot){
            j--;
        }
        //if we are here, it likely means we need to swap values
        //check that i hasn't gone beyond j
        if(i<=j){
            //simple swap
            temp = theArray[i];
            theArray[i] = theArray[j];
            theArray[j] = temp;
            //we just swapped values, so we don't need to check them again, so continue
            i++; 
            j--;
        }
    }
    //now check if parameter left is < j 
    //if left has gone beyond j, it means we no longer need to further sort
    if(left<j){
        //rinse and repeat
        quickSort(theArray, left, j);
    //and check that i is still less than right parameter 
    }if(i < right){
        //rinse and repeat
        quickSort(theArray, i, right);
    }

}

用法：

//you can amend this code so you don't have to pass in an array
quickSort(theArray, 0, theArray.length-1);

一旦您理解了快速排序的目的，这就相当简单了。不要对此感到压力，休息 15 分钟，观看算法的图形表示，并思考代码应该如何运行以及它试图实现什么。回到这里，查看代码，然后开始实现它。冲洗并重复！祝你好运！

另外（不确定你的考试布局如何）但你也可以提到，为了接近足够的保证 O(n log n) 的运行时间，你真的应该事先 shuffle the array。

快速排序堆栈溢出错误

Quicksort Stack overflow error

java

stack-overflow

recursion

quicksort