使用中間元素作爲支點進行快速排序的最壞情況的上限是多少？

-2

如果您選擇中間元素（位於中間位置的元素，而不是中值位置）作爲關鍵點，最差情況下的快速排序最緊的上限是多少？使用中間元素作爲支點進行快速排序的最壞情況的上限是多少？

來源

2014-03-03 user2331262

中間位置或中間位置的項目？ – user2357112

最糟糕的情況總是n平方，如果通過中間元素你的意思是中位數元素，那麼它不是最壞的情況了 – Leo

在中間位置的項目不是中位數 – user2331262

使用線性時間中值樞紐選擇（和@n.m.的評論）的確定性快速排序具有O（n log n）最差情況下的性能。

http://en.wikipedia.org/wiki/Quicksort#Selection-based_pivoting

來源

2014-03-03 05:58:37

你總是可以將你的數組分成三部分：'，'== pivot'和'> pivot'。 –

「確定性快速排序總是存在O（n^2）最差的情況。」 - 使用隨機性的人也是如此，只是除非你知道要生成的「隨機」數字（即PRNG的種子），否則不能構造所述最壞情況。雖然我不確定爲什麼你提到你的示例輸入是最糟糕的情況，因爲它也會是使用隨機性的，並且它不是使用衆所周知的優化利用重複的最壞情況。 – Dukeling

@ n.m。你是對的，我忘了這個明顯的伎倆。使用線性時間中值選擇算法，可以得到O（n log n）。 –

如果中間元素你指的是輸入數組的中位數則即使在最差情況下的時間複雜度爲O(nlogn)，但如果你的意思是排序的數組的中間元素則是在最壞的情況下O(n^2)，因爲它在最壞情況下會導致不平衡分區0：n-1。但在平均情況下，它仍然是O(nlogn)

來源

2014-03-03 06:49:10

快速排序的最差情況是O（n2）。平均情況是O（nlogn）。

O（n2）是最壞情況的上限。 O（nlogn）對於預期情況是嚴格的限制。

來源

2017-11-09 11:09:51 lemonader

使用中間元素作爲支點進行快速排序的最壞情況的上限是多少？

回答

相關問題