推 PsMonkey:純演算法角度評論的話，很難超越它吧？ 12/14 01:10
推 netsphere:排序法的效能最快也只能到O(NlogN) quick已經達到了 12/14 02:16
→ netsphere:所以就算有超越quickSort的SORT 也快不了多少的~ 12/14 02:20
→ netsphere:我覺得quicksort的對手是Merge sort 跟 Heap sort吧XD 12/14 02:22
推 OOJ:應用comparison tree形式的sorting可以證明最優是 NlogN 12/14 10:46
→ OOJ:要打破的話就要用其他方法..前年看到一篇NloglogN的..@@".. 12/14 10:47
推 ledia:NloglogN ? 應該有特定限制吧? 12/14 11:41
→ ledia:一般來說, 混合式會是比較強力的 12/14 11:42
→ ledia:用統計來看, 多少筆資料量以下的用 insertion, 多少以上用 12/14 11:43
→ ledia:quicksort 這樣 12/14 11:43
→ ledia:如果複雜度沒得改進, 那麼就要改常數 12/14 11:44
推 calais007:comparison and swap的sort很難比quick sort好 12/14 13:48
推 byronhc:quickSort 最差複雜度不也是 n^2 嗎？？ 12/14 16:47
→ byronhc:quickSort 的平均複雜度才是 NlogN ?? 12/14 16:47
→ byronhc:值有範圍的話 counting sort 不是最快 N 嗎？ XD 12/14 16:48
推 softwind:請問OOJ NloglogN的是哪一種演算法？ 12/14 17:01
推 ledia:counting sort 的限制除了值有範圍, 還要多用記憶體 12/14 17:42
→ 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
推 ledia:是有看到一篇 Deterministic Sorting in O(nloglogn) Time 12/15 09:30
→ ledia:and Linear Space 的 12/15 09:30
→ ledia:不過那是 integer sorting 12/15 09:30
推 cplusplus:整數排序的話 好像早就有了 好像還有更好的 12/16 18:37
推 colawei:丟到HashingTable中最快.只要O(n).以空間換取時間XD 12/17 13:44
推 cplusplus:樓上丟進去後怎麼從小取到大? 問題還很多吧~? 12/18 02:03
推 colawei:HashingTable建立時間O(n),搜尋時間O(1).沒有錯吧. 12/18 17:39
→ colawei:從頭找到尾需要搜尋整區段的時間->O(n),結果最後還是O(n) 12/18 17:42
推 colawei:修正一下.全部是 O(n+e)= O(n) 12/18 17:48
推 ledia:不能這樣算呀, input size 的 n 跟 hash size 的 n 是不同的 12/18 22:01
→ ledia:照你的 hash table 法, 不就每個可能的值都要有一格? 12/18 22:02
推 colawei:這個本來就只算到n,就算再分解e=n+k,O(2n+k)結果還是O(n) 12/18 22:10
→ colawei:一個值一格沒錯,所以我才說以空間換取時間呀XD 12/18 22:11
推 ledia:可以講詳細點嗎? 好像跳太快... 看不出搜尋整段的 e 是啥 12/19 02:21
→ ledia:舉個例子也許比較快? 12/19 02:22
推 colawei:參考:依座號排序學生資料、點名程式... 12/19 17:49
→ colawei:當n(資料筆數)>e(總位址數)會造成OverFlow,所以n必須<=e 12/19 17:49
→ colawei:當n接近e時,k(未用位址)就會接近0,所以結果O(2n+k)=>O(n) 12/19 17:50
推 OOJ:嗯..我看的是ACM "Sorting in linear time?" 這一篇~ 12/24 02:09
→ OOJ:要擺脫nlogn 就不能完全倚賴用比較的方式來完成sorting 12/24 02:10
推 drkkimo:colawe到底在講什麼 01/20 01:24
推 colawei:我只是想說.QSort並非在任何情況下都是最佳解.如此而已. 01/22 18:58
推 doggingg:quick sort 最棒!!!!!! 05/07 15:06