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