需要C++中的快速排序算法（嘗試）的幫助

Question

我試過了一堆不同的方法來寫這個，但大多數時候我陷入了一個無限循環。 這個版本的代碼根本沒有排序，我不知道問題是什麼。

void quickSort(int unsorted[], int left, int right) { 
     int i = left, j = right; 
     int pivot = (left + right)/2; 

     while (i == pivot || j == pivot) { 
      if (unsorted[i] >= unsorted[pivot] && unsorted[pivot] >= unsorted[j]) 
       swap(unsorted[i], unsorted[j]); 

      if (i < pivot) 
       i++; 
      if (j > pivot) 
       j--; 
     }; 

     if (left < j && unsorted[left] != unsorted[j]) 
      right = pivot, quickSort(unsorted, left, right); 
     if (i < right && unsorted[right] != unsorted[i]) 
      left = pivot +1, quickSort(unsorted, left, right); 

} 

unsorted是填充有從0 100個隨機值200

我爲更新緩慢遺憾的陣列。 關於代碼，我重新編寫了大部分代碼。 這是它看起來像現在：

void quickSort(int unsorted[], int left, int right) 
{ 
    int i = left, 
     j = right, 
     count = 0; 
    int pivot = (left + right)/2; 

    do 
    { 
      while (unsorted[i] < unsorted[pivot]) 
       i++; 
      while (unsorted[j] > unsorted[pivot]) 
       j--; 

      if (unsorted[i] >= unsorted[j] && i <= j) 
      { 
       swap(unsorted[i], unsorted[j]); 
       i++; 
       j--; 
       count++; 
      } 
      if (i == pivot && unsorted[pivot] < unsorted[j] && count == 0) 
      { 
       swap(unsorted[i], unsorted[j]); 
       i++; 
       j--; 
       count++; 
      } 
      if (j == pivot && unsorted[pivot] < unsorted[i] && count == 0) 
      { 
       swap(unsorted[i], unsorted[j]); 
       i++; 
       j--; 
       count++; 
      } 

      if (i == j && unsorted[i] > unsorted[pivot] && count == 0) 
      { 
       swap(unsorted[i], unsorted[pivot]); 
       i++; 
       j--; 
       count++; 
      } 
      if (i == j && unsorted[i] < unsorted[pivot] && count == 0) 
      { 
       swap(unsorted[i], unsorted[pivot]); 
       i++; 
       j--; 
      } 

      count = 0; 

    } while (i < j); 

    if (left < j) 
     quickSort(unsorted, left, j); 
    if (i < right) 
     quickSort(unsorted, i, right); 

} 

我已經一遍又一遍地用10個隨機值嘗試這種代碼，它工作的大部分時間。有些情況下它不起作用，我試圖找出什麼時候。

時它不工作的一個例子是當值是：160，151，159，112，如圖7所示，121，105，48，186

解決它。刪除了很多代碼，使它更簡單，但至少可以工作。 甚至不知道如果u可以稱之爲快速搜索了，但這裏是最後的版本：

void quickSort(int unsorted[], int left, int right) 
{ 
    int i = left, 
     j = right; 
    int pivot = right; 

    do 
    { 
     while (unsorted[i] < unsorted[pivot]) 
      i++; 
     while (unsorted[j] > unsorted[pivot]) 
      j--; 

     if (unsorted[i] >= unsorted[j] && i <= j) 
     { 
      swap(unsorted[i], unsorted[j]); 
      i++; 
      j--; 
     } 
    } while (i < j); 

    if (left < j) 
     quickSort(unsorted, left, j); 
    if (i < right) 
     quickSort(unsorted, i, right); 
} 

Answer 1

你沒長1

得到那個工作的陣列上測試你的函數，然後嘗試長度的數組2.

一旦這樣的工作，有一個很好的機會，它會當你給它長度的陣列工作3.

編輯：

獎勵用於包括可再現的例子。

此代碼在遞歸之前失敗。第一步是選擇一個pivot元素並移動一些元素，直到pivot元素不小於它的左邊任何一個，並且不超過它的右邊的任何元素。你的代碼失去了它認爲哪個元素是pivot元素的軌道;它掉出元素，但似乎認爲位置仍然是關鍵。嘗試使用鉛筆和紙製作算法，你會明白我的意思。

Answer 2

沒有看到swap，我的第一直覺是你的swap按值接受它的參數。即它交換兩個副本，而不是參數本身。

Answer 3

此檢查覺得奇怪，我

while (i == pivot || j == pivot) 

是不是應該至少

while (i != pivot && j != pivot) 

附：我認爲這不會是唯一的問題，但一開始...

Answer 4

哦，親愛的。我很抱歉喬，但事情看起來不太適合你的代碼。它需要許多計算血管手術，即使如此，我也不確定它會如何。讓我們來寫一個處方，我會讓你使用手術刀：

1. 如果left> = right，則返回。不要惹一個元素的數組。
2. 用你最左邊的元素交換你的元素（最右邊的也很好，但我必須選擇一個）。最後，您會將其交換到分區之間的正確位置。您可以通過將最左邊的元素（包含您的透視圖）與最左邊的分區的最右邊元素交換來做到這一點，如下一步所示。

3. 現在我們需要進行分區。讓我們來做一個我們能想到的最簡單的分區。下面是我剛剛開始使用quicksort時建議的一個：[ < pivot | >= pivot | unsorted ]。這是我們每一步都想要的不變性。一開始，所有東西都在未分類的分區中。最後，未分類的分區中將沒有任何內容。我們應該怎麼做？

   1. 從陣列中的left+1到right環路。
   2. 如果元素小於主元，我們用正確的交換將它添加到[ < pivot ]分區（我留給你 - 你會想要跟蹤左邊兩個分區之間的邊界）。如果不是，我們繼續前進。
4. 將主元放置到位後，您的陣列應看起來像[ < pivot | pivot | >= pivot ]。快速排列最左邊和最右邊的分區和事物應該真的在查找這個代碼。

嘗試像[ < pivot | unsorted | >= pivot ]分區（如果正確完成，速度會更快）等更加奇妙的事物。我認爲你目前的實現是試圖進行這種分區，但除非我或j指向一個等於主元的元素，否則不會進行任何交換。這種分區比較棘手，我建議我們在進入任何種族之前給你的代碼一個脈衝。

這會希望能夠讓你的代碼變得有形，但它只會是一個非常基本的快速排序。您應該研究Bentley-McIlroy分區和選擇方法以使其更加先進。