楼主:
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)