這個QuickSort實現有什麼問題？

-1

我無法猜測我的代碼有什麼問題。輸入：10，7，8，9，1，5 OUTPUT：5 7 9 8 10 1這個QuickSort實現有什麼問題？

public class QuickSort { 

    public static void quickSort(int arr[], int p, int r) { 

     if (p < r) { 
      // System.out.println(p+" "+r); 
      int q = partition(arr, p, r); 
      quickSort(arr, p, q - 1); 
      quickSort(arr, q + 1, r); 
     } 
    } 

    public static int partition(int arr[], int p, int r) { 
     int pivot = arr[r]; 
     int i = p - 1; 
     for (int j = p; j < r - 1; j++) { 
      // System.out.println("j"); 
      if (arr[j] <= pivot) { 
       i = i + 1; 
       int temp = arr[i]; 
       arr[i] = arr[j]; 
       arr[j] = temp; 
      } 
     } 
     int temp = arr[i + 1]; 
     arr[i + 1] = arr[r]; 
     arr[r] = temp; 
     return i + 1; 
    } 

    static void printArray(int arr[]) { 
     int n = arr.length; 
     for (int i = 0; i < n; ++i) 
      System.out.print(arr[i] + " "); 
     System.out.println(); 
    } 
}

請明晰我的疑問，在哪裏兌換代碼，以便它工作正常。

來源

2016-03-15 naveen

'partition'的返回值的確切語義是什麼？ – Codor

你沒有迭代到循環的最後（最後一個元素）。因此，分區函數不會正確地將元素分離爲較小的左側的樞軸和更大的樞軸右側。

您的循環

for (int j = p; j < r - 1; j++) {

變化

for (int j = p; j <= r - 1; j++) {

現在是工作的罰款。請看這裏Ideone

來源

2016-03-15 15:59:01 FallAndLearn

偉大的人..它的工作。感謝您的快速回復。 – naveen

請閱讀[回答]。你應該解釋爲什麼需要這種改變。 –

@JimGarrison謝謝。我現在已經完成了。 – FallAndLearn

這個QuickSort實現有什麼問題？

回答

相關問題