滯留在隨機轉動

Question

一個簡單的快速排序實現我檢討算法的東西，停留在簡單的快速排序算法的實現在java中

import java.util.Arrays; 
import java.util.Random; 

public class QuickSort { 
    int arr[]; 
    boolean randomPick; 
    Random rand = null; 

    public QuickSort(int[] inputArray) { 
     arr = inputArray; 
     randomPick = false; 
    } 

    public QuickSort(int[] inputArray, boolean random) { 
     arr = inputArray; 
     if (random) { 
      randomPick = true; 
      rand = new Random(System.currentTimeMillis()); 
     } 
     else { 
      randomPick = false; 
     } 
    } 

    public int[] sort() { 
     int start = 0; 
     int end = arr.length - 1; 
     try { 
      _sort(start, end); 
     } 
     catch (StackOverflowError e) { 
      System.out.println("StackOverflow: " + Arrays.toString(arr)); 
     } 
     return arr; 
    } 

    private void _sort(int start, int end) { 
     int i = start; 
     int j = end; 
     int pivotLoc; 
     if (!randomPick) { 
      pivotLoc = (j + i)/2; 
     } 
     else { 
      pivotLoc = rand.nextInt(j - i) + i; 
     } 
     int pivot = arr[pivotLoc]; 
     while (i < j) { // swapping numbers around the pivot 
      while (arr[i] < pivot) { 
       i++; 
      } 
      while (arr[j] > pivot) { 
       j--; 
      } 
      if (i < j) { 
       int t = arr[i]; 
       arr[i] = arr[j]; 
       arr[j] = t; 
       i++; 
       j--; 
      } 
     } 
     if (i - start > 1) { 
      _sort(start, i); 
     } 
     if (end - i > 1) { 
      _sort(i, end); 
     } 
    } 
} 

的代碼都可以選擇中間的數字爲支點或隨機選擇一個數字作爲數據透視表，並通過循環調用_sort對數組進行排序。它在第一種情況下工作，但在第二種情況下失敗。

的情況是：當它到達一個子陣列，因爲這{3,5,5}，我==啓動== 0和j ==端== 2。最後5和5交換，我變成2，j變成1（i ++和j--）。然後，因爲i - start>1它會一遍又一遍地調用_sort並最終喚起stackoverflow錯誤。然而，錯誤應該發生在第一種情況下（固定樞軸），至今尚未發生......

我不知道我的代碼有什麼問題。我知道閱讀其他人編寫的代碼並不是一種樂趣，但有任何幫助？

Answer 1

你犯了個小錯誤在你的遞歸條件下，無論是start和end比較反對i，則start應當針對j

您有：

if (i - start > 1) { 
     _sort(start, i); 
    } 
    if (end - i > 1) { 
     _sort(i, end); 
    } 

需要是：

if (j > start) { 
     _sort(start, j); 
    } 
    if (end > i) { 
     _sort(i, end); 
    } 

而你的i和j比較需要允許等於：

// here ----v 
     if (i <= j) { 
      int t = arr[i]; 
      arr[i] = arr[j]; 
      arr[j] = t; 
      i++; 
      j--; 
     }