作者:
MBS550L (li)
2021-06-16 13:53:25大家好
小弟在測試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
作者:
ckvir (ckvir)
2021-06-16 13:59:00是每次嗎？應該和選的 pivot 位置有關
作者:
MBS550L (li)
2021-06-16 14:06:00樓上大大是每次沒錯，我的快排都是選v[0]當pivot
quick sort 在 pivot 選的最差的情況下是 O(n^2)而 merge sort 是很穩定的 O(n*logn)
作者: paintlife08 2021-06-16 15:51:00
第131、136行，陣列v好像都事先被第126行排序了.
作者:
MBS550L (li)
2021-06-16 18:15:00各位不好意思= = 我m-sort的code有問題，不過無法自刪就給大家當笑話看吧哈哈 debug之後q-sort是最快的沒錯...
作者:
final01 (牛頓運動定律)
2021-06-16 19:21:00有沒有quick sort不是最快的八卦XD
作者:
Lipraxde (Lipraxde)
2021-06-16 20:03:00基於比較的排序法的話...可以這麼說吧
特殊狀況下是有比 quick sort 還快的排序啊，比如 distribution counting 是 O(N)