與快速排序算法混淆C＃

我一直在研究如何在C＃中爲大學做快速排序。我幾乎可以工作。只有幾個數字沒有按正確的順序出現。 array：1,5,8,6,7,3,2,4,9 「sorted」into：1,5,4,6,2,3,7,8,9 instead of 1,2， 3,4,5,6,7,8,9。不知道在哪裏，我在我的代碼會錯：與快速排序算法混淆C＃

int[] array4 = { 1, 5, 8, 6, 7, 3, 2, 4, 9}; 
QuickSort quick = new QuickSort(); 
quick.Quicksort(array4, 0, array4.Length - 1); 

public void Quicksort(int[] array, int left, int right) 
{ 
     int pivot, temp;      
     pivot = array[(left + right/2)]; 
     do 
     { 
      while ((array[left] < pivot) && (left < right)) 
       left++; 

      while ((pivot < array[right]) && (right > left)) 
       right--; 
      if (left <= right) 
      { 
       temp = array[left]; 
       array[left] = array[right]; 
       array[right] = temp; 
       left++; 
       right--; 
      } 
     } 
     while (left <= right); 

     if (left < right) Quicksort(array, left, right);    
     }    
}

感謝

來源

2016-12-03 Jonathan Mitchell

通常，當發生這種情況時，您不會在數組中的所有值中逗留。嘗試更改輸入數據並將'1'移動到列表的末尾。 – jdweng

您需要進行兩個遞歸調用，一個用於左側分區，另一個用於右側。 – Lee

在你快速排序的方法，因爲李的評論所指出的，你是不是調用帶有的左側和右側部分的快速排序法分區/樞軸。

首先我相信你是不是在該行得到適當的支點：

pivot = array[(left + right/2)];

以上，師會先發生，所以它會分「右」兩個再加入到「左」。這會給你一個錯誤的關鍵。它應該是：

pivot = array[(left + right)/2];

其次，當你進入快速排序的方法，你給出的起始索引值（左/右），並且使用這些變量來獲得下一個支點。當你改變它們時，這將拋棄「左」和「右」STARTING索引。因此，您需要複製這些STARTING值並使用複製的值創建下一個分區/數據透視表。

以下是我對您的代碼所做的更改，它似乎正常工作。

public static void Quicksort(int[] array, int left, int right) 
{ 
    int pivot, temp; 
    pivot = array[(left + right)/2]; 
    int originalLeft = left; 
    int originalRight = right; 
    do 
    { 
    while (array[left] < pivot) 
     left++; 

    while (pivot < array[right]) 
     right--; 
    if (left <= right) 
    { 
     temp = array[left]; 
     array[left] = array[right]; 
     array[right] = temp; 
     left++; 
     right--; 
    } 
    } 
    while (left <= right); 

    // note that the original left and right values are needed here 
    if (originalLeft < right) 
    Quicksort(array, originalLeft, right); 
    if (left < originalRight) 
    Quicksort(array, left, originalRight); 
}

希望這會有所幫助。

來源

2016-12-03 20:01:28 JohnG

你的建議已修復它。我看到我要去哪裏錯了。乾杯！ –

與快速排序算法混淆C＃

回答

相關問題