作者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/cn.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