即使分區（）之後的樞軸的最終位置不是它在排序數組中的位置，Hoare的快速排序如何工作？

Question

所有變量名都來自Quicksort's wikipedia page的Lomuto's和Hoare的快速排序僞代碼。

如果p就是由partition函數返回，霍爾分他從陣列到lo和p從p+1到hi，而Lomuto分他從陣列到lo和p-1從p+1到hi。

我可能是錯關於這一點，但快速排序的理念是...

1. 以一個元素在子陣列（支點）。
2. 以這樣的方式重新排列子陣列，即所有元素左側的元素都小於主元，並且主元右側的所有元素都大於主元。
3. 將數組除以數據點。重複這兩個較小子子陣列的過程。繼續這樣做直到遇到只有一個或更少元素的數組，因爲它已經被排序。

我覺得Hoare的partition比Lomuto更容易理解。霍爾的分區只是指示我們從左端和右端開始，並繼續向對方移動。如果左標記遇到比樞軸更大的元素，則左標記暫停，並等待右標記找到比樞軸小的元素。然後他們交換元素，以便左標記具有更小的元素，右標記具有更大的元素。他們繼續這樣做直到他們見面。非常簡單。

Lomuto的partition，可以被視爲一種蛇，由兩部分組成，頭部和尾部。樞軸是固定的（我通常把最後一個元素作爲Lomuto的樞軸）。蛇從左側開始，並在最後一個元素之前停止。當蛇遇到比樞軸小的元素時，該元素進入尾部並且尾部的長度增加。當發現一個大於主元的元素時，該元素會進入蛇的頭部。最後，樞軸位於尾部和頭部之間。這很清楚，但不像霍爾的partition那樣直觀或有效（在某些情況下）。

讓我感到困惑的是，Hoare的分區並不能確保partition之後的樞軸位置已經運行，它將在最終的排序數組中位置。我可以在霍爾的分區所承認的唯一模式是i處在樞軸的最終位置和j要麼i或i-1，j和i是左，右標誌。

但是，Lomuto的分區保證它。所以，當我退後一步看看更大的圖片時，Lomuto將數組從lo分成p-1和p+1到hi是合理的。但是，我不明白霍爾怎麼可以將他的數組從lo分成p和p+1到hi，彌補了他的分區沒有把它的支點放在合適的地方。

Answer 1

我一直在通過Hoare的quicksort查看示例和排序數組。我想我在霍爾的分區算法中找到了另一個有趣的模式。這可以解釋爲什麼霍爾的方法有效。 Lomuto將該陣列分成三個部分;小於樞軸的元素，樞軸，大於樞軸的元素。我認爲霍爾看待事情的方式不同。他將陣列分成兩個部分;小於該樞軸的元素，元素等於或大於樞軸。我陷入陷阱之一是Lomuto的分區返回樞軸的最終位置，而霍爾的分區返回樞軸的最終位置之前的位置。這就是爲什麼Lomuto然後從lo快速排序到p-1，而霍爾快速排序從lo到p。可以得出的另一個推論是，如果Hoare的partition返回i而不是j，那麼我們會將陣列分成兩部分 - 從lo到i-1和從i+1到hi，就像Lomuto一樣。而我只花了4個小時才明白這一點。