作者polomoss (小泽)
看板Grad-ProbAsk
标题[理工] [资结]-sort
时间Thu Dec 17 11:01:26 2009
请问一下，当资料量很大的时候
排序速率: Quicksort > Mergesort > Heapsort
是为什麽? 是由程式run出来的结果，还是有定理或什麽可以证明
题目问why，不知道怎麽解释
--
┌这篇文章让您觉得？─────────────────────────────┐
│ │
│ 一"一 \ / >\\\< ╯ ╰ ∩ ∩ ▁ ▁ ＞＿＜ ㄧ ㄧ+ │
│ 皿 ε □ ▽ ▇Δ ▇ ╰╯ ╯ │
│ 北七 乱喔 害羞 莎笅 爽啦 哭爸 ＸＤ 科科 │
└──────────────────────────────────────┘
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.116.14.2
1F：推 FRAXIS:定理的话 已经有人证明这三种sort在averge case情况下 12/17 12:32
2F：→ FRAXIS:的复杂度 包含系数都可以算出来 12/17 12:33
3F：→ polomoss:所以除非知道定理，不然考试没办法证明出来是吧~? 12/17 18:16
4F：→ NOtWorThy:跟计组第7章有关系 12/17 19:24
5F：推 FRAXIS:我觉得他只是要你申论吧 看这三种演算法到底是快在哪.. 12/17 20:02
6F：→ FRAXIS:像Heapsort就说他还要维持一个heap的形状 实做比较复杂 慢 12/17 20:02
7F：→ FRAXIS:Mergesort要一个额外阵列搬来搬去 所以比不上quicksort 12/17 20:03
8F：→ doom8199:怎麽怪怪的... Quicksort 应该是三者里面最慢的 12/17 21:18
9F：推 eddie780217:楼上 Qiucksort在Average case下的确是最快的 12/17 22:34
10F：→ eddie780217:打错 是Quicksort才对= = 12/17 22:36
11F：→ doom8199:但它的 worst case 并非 O(nlogn) 12/17 23:07
12F：→ doom8199:对程式的稳定性来说， Mergesort 和 Heapsort 再怎麽糟 12/17 23:12
13F：→ doom8199:也只会到 O(nlogn) .Quicksort 快在有可能比 O(nlogn) 12/17 23:13
14F：→ doom8199:还小，但只对特定情况才会如此 12/17 23:14
15F：推 eddie780217:是指"Average case"的情况下 Quicksort才最快 12/17 23:16
16F：→ doom8199:恩，我知道， 只是我觉得实用性应该要倒过来 OTZ 12/17 23:21
17F：→ converse2006:其实圣经本上面有平均时间的数据 Quick sort稳稳领先 12/18 00:33
18F：→ ssccg:Average case下快为什麽实用性要倒过来 12/18 06:57
19F：→ ssccg:程式的稳定性也不是用worst case当唯一指标吧 12/18 06:58
20F：→ ssccg:Quicksort并不是快在有可能比O(nlogn)小，而是在大部分case 12/18 07:00
21F：→ ssccg:比另外两者快常数/低order的时间 12/18 07:04
22F：→ ssccg:注意是大部分，反而应该说在特定情况才会比较慢 12/18 07:05