3回答

liuyubobobo

2016-12-10

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

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模式测测速度看？：）

0

0

liuyubobobo

2016-12-06

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

0

0

liuyubobobo

2016-12-06

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

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

0

5

哎呦不错哦12

回复

liuyubobobo

好的老师，我在看看

2016-12-06

共5条回复