关于排序算法效率的问题

Question

老师您好。我用的是VS 2013和win 10，用的数据量是100万个。但是在绝大部分情况下归并排序的自底向上是最优的，普通的快排和优化了的快排都比归并排序差太多，只有在重复多键值时，三路的快排才比归并排序要好。和你课程上的快排效率差距还是蛮大的！有点不解。

Answer 1

liuyubobobo 2016-12-10 07:10:03

看了一遍你的代码。你的快速排序在随机化的过程中，犯了个小错误。

swap(arr[l], arr[rand() % (r - l + 1) + l]);

你写成了

swap(arr[l], arr[rand() % (r - l + 1) + 1]);

在[0...r-l+1)这个范围内随机化以后，你需要加上左边界l（left）以保证随机化了一个[l...r]这个区间的值，但你是加的一。根据partition的性质，每次你都将arr[l]和一个比arr[l]小的多的元素交换了位置。所以每次的partition的过程都将整个数组分割成了完全不平衡的两部分，拖慢了速度。

事实上，在这种情况下，你的快速排序是失败的。你可以使用比如30个元素的小数组打印排序结果看一下。（不要使用16个元素以下的数组，因为你的优化，在16个元素以下的数组是使用插入排序，结果是正确的！）或者在debug模式下运行，assert(isSorted(arr,n))这个断言就会报错。

但是你在release模式下运行，断言被忽略了，直接运行程序，给出了程序执行的时间。

改正这个错误。swap可以使用std::swap。确保在debug模式下程序没有问题，再使用release模式测测速度看？：）

Answer 2

liuyubobobo 2016-12-06 17:45:22

如果自己还是找不到问题，请微信联系我一下：liuyubobobo 注明：算法

Answer 3

liuyubobobo 2016-12-06 17:23:17

使用VS的同学，在做算法性能测试的时候，请一定使用Release模式运行程序！不然，VS会在Debug模式下的标准库中做一些其他事情，另外运行器也使用的是未优化的版本，从而拖慢算法的执行速度，使得算法性能的比较不准确。可以尝试测试一下，在VS Debug模式下，std::swap的速度非常慢，甚至比自己写的swap还要慢。而我们在归并排序中，没有使用std::swap，所以在debug模式下就会比快排还要快了。

请在VS窗口上方的tool bar上，将运行模式调为Release，再试试看：）

• 提问者 哎呦不错哦12 #1

  是的老师，实在release下跑的，但是效率还是比较低
  

• liuyubobobo 回复 提问者 哎呦不错哦12 #2

  不太应该哦 那感觉是你的快排实现问题了？用我的代码在release模式下跑一下，也是这样的结果吗？ https://github.com/liuyubobobo/Play-with-Algorithms

• 提问者 哎呦不错哦12 回复 liuyubobobo #3

  我是边看课程然后跟着你的代码手动敲的，一开始我也以为是我代码出问题了。然后还和课程上的代码对了一遍，最后直接把变量名和所有步骤都和你的弄一样，还是不行。老师，会不会是你说的标准明明空间中swap函数的问题吗？

点开查看后面2条评论