在快速排序中使用中值選擇？

我對Quicksort有個小問題。在選擇數組的最小值或最大值的情況下，由於數組大小僅減少1，所以分區的樞軸值非常低效。在快速排序中使用中值選擇？

但是，如果我添加選擇該數組中位數的代碼，那麼我認爲Ii將會更有效率。由於分區算法已經是O（N），它會給出一個O（N log N）算法。

可以這樣做嗎？

2012-08-27 Dude

可以做些什麼？爲什麼不嘗試實施你的改變並找出答案？ –

我在問時間的複雜性。 – Dude

@Batman，我認爲sch暗示爲了找到中位數，你必須對數組進行排序。 –

您絕對可以使用線性時間中值選擇算法來計算快速排序中的支點。這給你一個最壞情況的O（n log n）排序算法。

但是，線性時間選擇的常數因子往往非常高，以至於實際上得到的算法比僅在每次迭代中隨機選擇主元的快速排序慢得多。因此，看到這樣的實現並不常見。

一種完全不同的方法來避免O（n ）最糟糕的情況是使用類似於introsort中的方法。該算法監視快速排序的遞歸深度。如果看起來算法開始退化，它將切換到一個不同的排序算法（通常是heapsort），並保證最壞情況下的O（n log n）。這使得整體算法O（n log n）沒有顯着降低性能。

希望這會有所幫助！

2012-08-27 19:34:48 templatetypedef

回答