作者PsMonkey (痞子軍團團長)
看板Prob_Solve
標題[轉錄][閑聊] 超越quickSort的sort是..?
時間Fri Dec 15 01:01:22 2006
※ [本文轉錄自 C_and_CPP 看板]
作者: XX9 () 看板: C_and_CPP
標題: [閑聊] 超越quickSort的sort是..?
時間: Wed Dec 13 23:15:49 2006
今天聽老師講到quick sort是近年最快的排序大法
不過這個記錄去年被打破了
請問一下 這個排序是...??
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.64.100.15
1F：推 PsMonkey:純演算法角度評論的話，很難超越它吧？ 12/14 01:10
2F：推 netsphere:排序法的效能最快也只能到O(NlogN) quick已經達到了 12/14 02:16
3F：→ netsphere:所以就算有超越quickSort的SORT 也快不了多少的~ 12/14 02:20
4F：→ netsphere:我覺得quicksort的對手是Merge sort 跟 Heap sort吧XD 12/14 02:22
5F：推 OOJ:應用comparison tree形式的sorting可以證明最優是 NlogN 12/14 10:46
6F：→ OOJ:要打破的話就要用其他方法..前年看到一篇NloglogN的..@@".. 12/14 10:47
7F：推 ledia:NloglogN ? 應該有特定限制吧? 12/14 11:41
8F：→ ledia:一般來說, 混合式會是比較強力的 12/14 11:42
9F：→ ledia:用統計來看, 多少筆資料量以下的用 insertion, 多少以上用 12/14 11:43
10F：→ ledia:quicksort 這樣 12/14 11:43
11F：→ ledia:如果複雜度沒得改進, 那麼就要改常數 12/14 11:44
12F：推 calais007:comparison and swap的sort很難比quick sort好 12/14 13:48
13F：推 byronhc:quickSort 最差複雜度不也是 n^2 嗎？？ 12/14 16:47
14F：→ byronhc:quickSort 的平均複雜度才是 NlogN ?? 12/14 16:47
15F：→ byronhc:值有範圍的話 counting sort 不是最快 N 嗎？ XD 12/14 16:48
16F：推 softwind:請問OOJ NloglogN的是哪一種演算法？ 12/14 17:01
17F：推 ledia:counting sort 的限制除了值有範圍, 還要多用記憶體 12/14 17:42
18F：→ ledia:跟 quicksort 比不公平啦 Orz 12/14 17:42
--
侃侃長論鮮窒礙 網站：
http://www.psmonkey.idv.tw
眾目睽睽無心顫 個人版：telnet://legend.twbbs.org
煢居少聊常人事
殺頭容易告白難 歡迎參觀 Java 版（@ptt.cc） \囧/
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.192.56
19F：推 ledia:是有看到一篇 Deterministic Sorting in O(nloglogn) Time 12/15 09:30
20F：→ ledia:and Linear Space 的 12/15 09:30
21F：→ ledia:不過那是 integer sorting 12/15 09:30
22F：推 cplusplus:整數排序的話 好像早就有了 好像還有更好的 12/16 18:37
23F：推 colawei:丟到HashingTable中最快.只要O(n).以空間換取時間XD 12/17 13:44
24F：推 cplusplus:樓上丟進去後怎麼從小取到大? 問題還很多吧~? 12/18 02:03
25F：推 colawei:HashingTable建立時間O(n),搜尋時間O(1).沒有錯吧. 12/18 17:39
26F：→ colawei:從頭找到尾需要搜尋整區段的時間->O(n),結果最後還是O(n) 12/18 17:42
27F：推 colawei:修正一下.全部是 O(n+e)= O(n) 12/18 17:48
28F：推 ledia:不能這樣算呀, input size 的 n 跟 hash size 的 n 是不同的 12/18 22:01
29F：→ ledia:照你的 hash table 法, 不就每個可能的值都要有一格? 12/18 22:02
30F：推 colawei:這個本來就只算到n,就算再分解e=n+k,O(2n+k)結果還是O(n) 12/18 22:10
31F：→ colawei:一個值一格沒錯,所以我才說以空間換取時間呀XD 12/18 22:11
32F：推 ledia:可以講詳細點嗎? 好像跳太快... 看不出搜尋整段的 e 是啥 12/19 02:21
33F：→ ledia:舉個例子也許比較快? 12/19 02:22
34F：推 colawei:參考:依座號排序學生資料、點名程式... 12/19 17:49
35F：→ colawei:當n(資料筆數)>e(總位址數)會造成OverFlow,所以n必須<=e 12/19 17:49
36F：→ colawei:當n接近e時,k(未用位址)就會接近0,所以結果O(2n+k)=>O(n) 12/19 17:50
37F：推 OOJ:嗯..我看的是ACM "Sorting in linear time?" 這一篇~ 12/24 02:09
38F：→ OOJ:要擺脫nlogn 就不能完全倚賴用比較的方式來完成sorting 12/24 02:10
39F：推 drkkimo:colawe到底在講什麼 01/20 01:24
40F：推 colawei:我只是想說.QSort並非在任何情況下都是最佳解.如此而已. 01/22 18:58
41F：推 doggingg:quick sort 最棒!!!!!! 05/07 15:06