3 回答

TA貢獻(xiàn)1811條經(jīng)驗(yàn) 獲得超6個贊
選擇隨機(jī)數(shù)據(jù)會最大限度地減少您遇到最壞情況O(n 2)性能的可能性(總是選擇第一個或最后一個會導(dǎo)致近似排序或接近反向排序的數(shù)據(jù)的最壞情況性能)。在大多數(shù)情況下,選擇中間元素也是可以接受的。
此外,如果您自己實(shí)現(xiàn)此功能,則有一些算法的版本可以就地工作(即不創(chuàng)建兩個新列表然后連接它們)。

TA貢獻(xiàn)1840條經(jīng)驗(yàn) 獲得超5個贊
嘿,我剛剛教過這堂課。
有幾種選擇。
簡單:選擇范圍的第一個或最后一個元素。(部分排序輸入不好)更好:選擇范圍中間的項(xiàng)目。(部分排序輸入更好)
但是,選擇任意元素會冒大規(guī)模將n數(shù)組分成兩個大小為1和n-1的數(shù)組的風(fēng)險。如果你經(jīng)常這樣做,你的快速排序可能會成為O(n ^ 2)。
我看到的一個改進(jìn)是選擇中位數(shù)(第一,最后,中期); 在最壞的情況下,它仍然可以轉(zhuǎn)到O(n ^ 2),但概率上,這是一種罕見的情況。
對于大多數(shù)數(shù)據(jù),選擇第一個或最后一個就足夠了。但是,如果您發(fā)現(xiàn)經(jīng)常遇到最壞情況(部分排序輸入),則第一個選擇是選擇中心值(對于部分排序的數(shù)據(jù),這是一個統(tǒng)計上很好的支點(diǎn))。
如果您仍然遇到問題,那么請走中間路線。
添加回答
舉報