2012年7月17日

快速排序、線性時間選擇

摘要: 快速排序是運用了分治思想的排序方式，具有O(NlogN)的平均時間復雜度，極端情況下時間復雜度為O(N^2)，跟冒泡排序一樣，但是快排的實際效率遠比最壞情況好很多。它的關鍵部分是一輪選擇（由Partition()函數完成）……所謂線性時間就是在平均O(N)的時間內找出無序序列中第k大的元素。它是以Partition()函數的劃分為依據的…… 閱讀全文

posted @ 2012-07-17 16:46 小鼠標閱讀(3719) | 評論 (1) | 編輯收藏

2012年4月

日

一

二

三

四

五

六

常用鏈接

隨筆分類(111)

隨筆檔案(127)

最新評論

1.?re: 線段樹
是這個樣子的，所以在OJ有時候“卡住”了也不要太灰心，沒準真的不是自己的原因呢。
加油，祝你好運啦！
--小鼠標
2.?re: 線段樹
對于編程競賽來說，Java所需時間一般為C/C++的兩倍。合理的競賽給Java的時間限制是給C/C++的兩倍。
--傷心的筆
3.?re: poj1273--網絡流
過來看看你。
--achiberx
4.?re: （轉）ubuntu11.10無法啟動無線網絡的解決方法
膜拜大神。。查了一個下午資料終于在這里解決了問題。。神牛說的區域賽難道是ACM區域賽。。？
--Hang
5.?re: 快速排序、線性時間選擇
博主，謝謝你的文章。你的方法可以很好的處理分區基準在數組中重復的情況，書上的方法遇到這種輸入會堆棧溢出。書上給出了解釋但給的方法貌似不簡潔。
--lsxqw2004

常用鏈接

隨筆分類(111)

隨筆檔案(127)

friends

最新評論

閱讀排行榜