Quicksort vs中位數漸近行爲

Question

Quicksort和Median使用相同的方法（分而治之），爲什麼他們有不同的漸近行爲？

這是快速排序可能不使用正確的支點？

Answer 1

如果您使用Hoare的原始select算法，您可以得到與Quicksort相同的糟糕的最壞情況性能。

如果您使用中位數的中位數，那麼您會限制最差的情況，但代價是在大多數典型情況下會變慢。

您可以使用中值的中位數來查找Quicksort的數據透視表，這將具有大致相同的效果 - 限制最差情況，但代價是在大多數情況下速度較慢。當然，對於排序（一般來說），每個分區操作是O（N），並且您期望執行有關log（N）分區操作的操作，因此您可以獲得大約O（N log N）的總體複雜度。

通過中值查找，您還希望執行大約O（log N）個步驟，但您只考慮上一步中可能包含中值（或四分位數等您所關心的）的分區。您預計這些分區的大小在每一步都會被分成大約兩個分區，而不是始終必須對整個輸入進行分區，因此您最終得到的整體約爲O（N）複雜度而不是O（N log N）。

[注意，本，我有點濫用大O表示法來表示預期複雜而大O真的應該代表上限（即，最壞情況下）的複雜性。]

Answer 2

當您使用方法partition在Quicksort（請參閱鏈接中的方法）來查找中位數時，基於此位置的具有正確位置的元素的方法返回索引，只需檢查包含中位數的選定部分。

例如，數組長度爲5，因此中位數爲3.分區方法返回2，因此您只需要檢查數組的上部2到5，而不是整個數組作爲Quicksort。