Quicksort：選擇樞軸實現Quicksort時，您需要做的一件事就是選擇一個數據透視表。但是當我看下面的偽代碼時，我不知道應該如何選擇樞軸。列表的第一個要素？別的什么？ function quicksort(array)
var list less, greater
if length(array) ≤ 1
return array
select and remove a pivot value pivot from array
for each x in array
if x ≤ pivot then append x to less
else append x to greater
return concatenate(quicksort(less), pivot, quicksort(greater))有人可以幫助我掌握選擇樞軸的概念，以及不同的場景是否需要不同的策略。
3 回答
楊魅力
TA貢獻1811條經驗 獲得超6個贊
選擇隨機數據會最大限度地減少您遇到最壞情況O（n 2）性能的可能性（總是選擇第一個或最后一個會導致近似排序或接近反向排序的數據的最壞情況性能）。在大多數情況下，選擇中間元素也是可以接受的。
此外，如果您自己實現此功能，則有一些算法的版本可以就地工作（即不創建兩個新列表然后連接它們）。
慕斯709654
TA貢獻1840條經驗 獲得超5個贊
嘿，我剛剛教過這堂課。
有幾種選擇。
簡單：選擇范圍的第一個或最后一個元素。（部分排序輸入不好）更好：選擇范圍中間的項目。（部分排序輸入更好）
但是，選擇任意元素會冒大規模將n數組分成兩個大小為1和n-1的數組的風險。如果你經常這樣做，你的快速排序可能會成為O（n ^ 2）。
我看到的一個改進是選擇中位數（第一，最后，中期）; 在最壞的情況下，它仍然可以轉到O（n ^ 2），但概率上，這是一種罕見的情況。
對于大多數數據，選擇第一個或最后一個就足夠了。但是，如果您發現經常遇到最壞情況（部分排序輸入），則第一個選擇是選擇中心值（對于部分排序的數據，這是一個統計上很好的支點）。
如果您仍然遇到問題，那么請走中間路線。
添加回答
舉報
0/150
提交
取消