我的quicksort桌面測試似乎不正確

Question

我目前正在練習quicksort，它現在工作得很好。但我可以找到一個失敗的例子（因爲它似乎是一個特例，我還沒有讀過它，這就是爲什麼我做錯了......不能解決它）。問題是，我想是因爲我選擇最小的元素作爲主元：

9 1 4 2 7 *0* (star mark means pivotelement) 

現在我設定i,j哪裏i將通過陣列（右移），直到它發現它比主元以上的元素。並且j將通過Array（向左移動）直到找到一個低於樞紐元素的元素。找到了，我們切換i和j顯示的元素。我們這樣做直到i和j交叉（又名「j在i」之前）。在這種情況下，我們切換元件i節目並索引i與主元......我現在不想描述整個算法也將是長期的問題..

9 1 4 2 7 *0* 
i  j  but now we cannot find a j that is lower than Pivotelement. What we do? 
       I would continue by switching i with pivotelement: 

*0* 1 4 2 7 9 
      j i But now is the Problem that i and j are in other positions 
       (j is before i). I have no idea.. Please clarify and help.. 

Answer 1

你有什麼好，你已經成功地轉動了。

樞軸處於正確的位置，樞軸的兩側滿足條件：左側的所有元素都較少，右側的所有元素都較大。 i指數在關鍵點的最後一步移動時處於不利的位置，但您不會在乎您打破了這一點，因爲無論如何您都完成了它。現在你遞歸併快速排序樞軸的左側和右側 - 除了沒有左側，所以在這個角落的情況下，你只是遞歸到右側。

Answer 2

快速排序工作在分區的概念。在每次迭代中，它會拾取一個pivot元素，並嘗試將其放置在最終放置的位置。

開始時i指針始終保持在索引-1（這顯然是不可能的，所以我們只給它賦值-1，並且只在我們增加它之後引用一個數組元素）。

所以在您的情況你得到的第一個循環之後，

0 1 4 2 7 9

這是所選擇的轉動部件的正確位置。

說明：由於i最初是在-1，你遞減j指針，直到你得到小於當前的主元（0）的元素。這將j一直帶到索引0（您需要將這些條件添加到代碼中以確保沒有非法內存空間被訪問）。

最後i+1（其中i仍然是-1）被替換爲pivot元素，所以有效的9被替換爲0和viola！

有關更全面的解釋，請參閱this鏈接。