快速排序堆棧溢出錯誤

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

但是，這給了我一個「java.lang.StackOverflowError的：空」的（在這裏）34號線可以，但是，通過與J-交換J值可以避免此錯誤1和我在第34行和第35行中的j.我真的嘗試了一切進入我的想法，但我真的不能想出一個解決方案：/

Answer 1

我認爲有更好的quicksort實現，這是我的嘗試附帶評論，希望能幫助你更好地記住它：

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日誌n），你真的應該shuffle the array事先。