Quicksorting整數數組實踐

Question

所以我有這個數組{3,1,4,1,5,9,2,6,5,3,5}

我使用的是中位數的三個方法來獲取的支點。

所以在這種情況下，這裏的中位數在左，中，右之間：3,9,5。所以這是5

我做的第一件事是確保樞軸位於最左邊。 現在我保留左邊的數字小於5，並將數字移到數組的最右邊。最終結果是：{3,1,4,1,2,3|5|5,9,6,5}

現在快速排列左側和右側的子陣列。

{3,1,4,1,2,3}有3位數並重新排列後，我得到{1,1,2,3,4}

{5,9,6,5}有5位數，我得到{5,5,9,6}如排序和相等數量更多的權利的結果。但是這個子陣不像第一個子陣列那樣排序。它只會在中位數爲6時起作用。那麼哪裏出錯了？謝謝。

Answer 1

您必須再次對{|5|5,9,6}（或{5|5|,9,6}）的右側子數組進行排序。中位數爲6，結果爲{5,6,9}（或{6,9}）。

另請注意，具有許多重複鍵的樸素Quicksort可能降級爲二次時間複雜度。有幾種方法可以檢測與主鍵相同的鍵，並將它們從遞歸排序的子排列中排除。