大家好
小弟在测试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

是每次吗？应该和选的 pivot 位置有关

楼上大大是每次没错，我的快排都是选v[0]当pivot

quick sort 在 pivot 选的最差的情况下是 O(n^2)而 merge sort 是很稳定的 O(n*logn)

你有验证过你写的两个sort的正确性了吗?

第131、136行，阵列v好像都事先被第126行排序了.

各位不好意思= = 我m-sort的code有问题，不过无法自删就给大家当笑话看吧哈哈 debug之后q-sort是最快的没错...

有没有quick sort不是最快的八卦XD

基于比较的排序法的话...可以这么说吧

特殊状况下是有比 quick sort 还快的排序啊，比如 distribution counting 是 O(N)