作者MBS550L (uu8nc)
看板C_and_CPP
標題[問題] Merge Sort v.s. Quick Sort
時間Wed Jun 16 13:53:25 2021
大家好
小弟在測試merge sort 與 quick sor時發現
在一百萬筆long int的case下測試多次發現
merge sort的平均速度約為70ms
而quick sort的平均速度約為130ms
差了將近一倍 怎麼會這樣?
我是用隨機的亂數輸入陣列
而為了不要元素有那麼多重複的
我是用rand()*rand()
為甚麼quick sort會比merge sort慢了將近一倍@@
這邊用的演算法都是最基礎的 沒有經過改良
還請各位大大幫我解惑了 查了許多資料都沒查到QQ
這是我的code
https://ideone.com/Glm92N
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 116.241.212.216 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1623822807.A.444.html
1F：→ ckvir: 是每次嗎？應該和選的 pivot 位置有關 06/16 13:59
2F：→ MBS550L: 樓上大大是每次沒錯，我的快排都是選v[0]當pivot 06/16 14:06
※ 編輯: MBS550L (116.241.212.216 臺灣), 06/16/2021 14:15:59
3F：推 windada2: quick sort 在 pivot 選的最差的情況下是 O(n^2) 06/16 15:08
4F：→ windada2: 而 merge sort 是很穩定的 O(n*logn) 06/16 15:11
5F：→ sarafciel: 你有驗證過你寫的兩個sort的正確性了嗎? 06/16 15:13
6F：推 paintlife08: 第131、136行，陣列v好像都事先被第126行排序了. 06/16 15:51
7F：→ MBS550L: 各位不好意思= = 我m-sort的code有問題，不過無法自刪就 06/16 18:15
8F：→ MBS550L: 給大家當笑話看吧哈哈 debug之後q-sort是最快的沒錯... 06/16 18:15
9F：→ final01: 有沒有quick sort不是最快的八卦XD 06/16 19:21
10F：→ Lipraxde: 基於比較的排序法的話...可以這麼說吧 06/16 20:03
11F：推 Schottky: 特殊狀況下是有比 quick sort 還快的排序啊， 06/17 04:36
12F：→ Schottky: 比如 distribution counting 是 O(N) 06/17 04:36