無法完美實現QuickSort

我想在java中編寫一個簡單的方法來執行int []上的快速排序，但我總是收到一個在結果中不合適的值。無法完美實現QuickSort

任何幫助瞭解我要去哪裏錯將不勝感激。以下是我的代碼：

public static void quickSort(int[] arr, int left, int right){ 
    if (left < right){ 
     int p = partition(arr, left, right); 
     quickSort(arr, left, p-1); 
     quickSort(arr, p+1, right); 
    } 
} 

public static int partition(int[] arr, int left, int right){ 
    int pivot = arr[left]; 
    int l = left+1; 
    int r = right; 
    while (l < r){ 
     while (l<right && arr[l] < pivot){ 
      l++; 
     } 
     while (r>left && arr[r] > pivot){ 
      r--; 
     } 
     if (l < r){ 
      int temp = arr[l]; 
      arr[l] = arr[r]; 
      arr[r] = temp; 
     } 
    } 
    arr[left] = arr[r]; 
    arr[r] = pivot;   
    return r; 
}

來源

2015-11-18 RajveerParikh

如果'right'等於'left + 1'會怎麼樣？這兩個元素交換時沒有任何密鑰比較。（哦，如果主鍵在arr [left]裏直到循環之後，比較'r> left'是多餘的。） – greybeard

你的代碼是完美的，但一定要給方法quickSort正確的值。

 int[] arr = .....; 
     int left = 0; 
     int right = arr.length - 1; 

    public static void quickSort(int[] arr, int left, int right){

來源

2015-11-18 20:55:24 Abdelhak

這正是我提供的參數。 – RajveerParikh

這兩條線是可疑：

quickSort(arr, p+1, right);

和

int l = left+1;

當取右側分區，你跳過陣列的第一個元素？一些示例測試用例及其輸出對添加會很有用。

來源

2015-11-18 21:17:44 Patrick

據我所知，我沒有跳過任何價值觀。當我使用調試器時，我也注意到它最初將它分類正確，然後再次切換它們。至少在第二個測試案例中。這是我試過的一個測試案例：輸入陣列：8 5 9 10 12 9 6 12 13 19 22 14 17 21 5 1 4 3 2 結果：1 2 3 4 5 5 6 8 9 9 10 12 12 13 17 14 19 21 22 第二個測試案例：輸入陣列：8 5 9 10 12 7 6 13 19 22 14 17 21 5 1 4 3 2 結果：1 2 3 4 5 5 7 6 8 9 10 12 13 14 17 19 21 22 – RajveerParikh

我改變了你的分區方法。我試圖做一些小改動，主要是爲了打破循環。

public static int partition(int[] arr, int left, int right) { 
    int pivot = arr[left]; 
    int l = left ; 
    int r = right+1; 
    while (true) { 
     while (arr[++l] < pivot) { 
      if (l >= right) 
       break; 
     } 
     while (arr[--r] > pivot) { 
      if (r <= left) 
       break; 
     } 
     if (l >= r) 
      break; 
     int temp = arr[l]; 
     arr[l] = arr[r]; 
     arr[r] = temp; 
    } 
    arr[left] = arr[r]; 
    arr[r] = pivot; 
    return r; 
}

我測試了以下情況，它工作。

int[] arr = { 9, 5, 10, 8, 2, 3, 4, 7, 6, 1 }; 
int[] arr = { 9, 5, 10, 8, 2, 9, 5, 10, 8, 2 }; 
quickSort(arr, 0, arr.length - 1); 
System.out.println(Arrays.toString(arr));

來源

2015-11-18 21:50:55

謝謝你。我無法理解爲什麼這會產生差異，但我會嘗試在我的代碼中實現它，看看它是否能實現。 – RajveerParikh

添加break語句以擺脫while循環似乎這樣做。不知道爲什麼這樣。 – RajveerParikh

以前的代碼無法檢查邊界條件，何時中斷或繼續。三個突破陳述就是這樣做的。以前的代碼正在執行值檢查和邊界檢查，但是新代碼正在檢查值的有效性，然後檢查邊界是否中斷或繼續。 –

Hoare分區方案在快速排序調用中使用p和p + 1。我將一個工作的C程序轉換爲Java。我將數據透視表切換到中間位置，所以排序或反向排序的數組並不是最壞的情況。

public static void quickSort(int[] arr, int left, int right){ 
    if (left < right){ 
     int p = partition(arr, left, right); 
     quickSort(arr, left, p); 
     quickSort(arr, p+1, right); 
    } 
} 

public static int partition(int[] arr, int left, int right){ 
    int pivot = arr[(left+right)/2]; 
    int l = left-1; 
    int r = right+1; 
    while (true){ 
     while (arr[++l] < pivot); 
     while (arr[--r] > pivot); 
     if (l >= r) 
      break; 
     int temp = arr[l]; 
     arr[l] = arr[r]; 
     arr[r] = temp; 
     } 
    } 
    return r; 
}

來源

2015-11-19 10:52:35 rcgldr

無法完美實現QuickSort

回答

相關問題