作者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