快速排序與中間元素爲支點

Question

我快速的體悟是

1. 選擇在極端樞軸元素（在這種情況下，我選擇中間的元素作爲 支點）
2. 初始化左右指針。
3. 找到大於樞軸的樞軸左側的第一個元素。
4. 類似地找到的第一個元素到比樞軸更小，3發現
5. 交換元件4
6. 重複3,4,5-除非左> =右樞軸的右側。
7. 重複整個事情的左側和右側的數組，因爲樞軸現在放置在它的地方。

我相信我在這裏失去了一些東西，很愚蠢。但以上似乎並沒有這個陣列工作：

8,7,1,2,6,9,10,2,11 pivot: 6 left pointer at 8, right pointer at 11 
    2,7,1,2,6,9,10,8,11 swapped 2,8 left pointer at 7, right pointer at 10 

現在是什麼？右側沒有小於6的元素。 7將如何去右邊6？

Answer 1

在左側和右側之間沒有前期劃分。尤其是，6不是師。相反，分區是左右指針相互靠近直到相遇的結果。結果可能是一方比另一方小得多。

你對算法的描述很好。它沒有任何地方說你必須停止在中間元素。只要繼續按照給定的方式執行它。

順便說一下：在排序過程中可能會移動元素元素。即使它已被移動，只要繼續與6進行比較即可。

更新：

確實有在你的算法描述了幾個小問題。一個是步驟3或步驟4需要包含等於的元素到關鍵點。讓我們把它改寫這樣的：

我快速的體悟是

1. 選擇一個支點值（在這種情況下，選擇中間元素的值），在極端
2. 初始化左右指針。
3. 從左側指針開始向右側移動，找到第一個大於或等於樞軸值的元素。
4. 類似地，起始於右指針和向左移動，找到的第一個元素，這是比樞軸值小
5. 在3發現交換元件和4
6. 重複3,4,5- 直到左指針大於或等於右指針。
7. 重複左側指針左側和右側兩個子數組的全部內容。

pivot value: 6, left pointer at 8, right pointer at 11 
8,7,1,2,6,9,10,2,11 left pointer stays at 8, right pointer moves to 2 
2,7,1,2,6,9,10,8,11 swapped 2 and 8, left pointer moves to 7, right pointer moves to 2 
2,2,1,7,6,9,10,8,11 swapped 2 and 7, left pointer moves to 7, right pointer moves to 1 
pointers have now met/crossed, subdivide between 1 and 7 and continue with two subarrays