【求助】关于堆排序、归并排序、快速排序的比较，到底谁快-CSDN论坛-真格学网-IT技术综合网站
【求助】关于堆排序、归并排序、快速排序的比较，到底谁快-CSDN论坛
来源：互联网 &责任编辑:小易 &
本网有用户碰到这样的问题：【求助】关于堆排序、归并排序、快速排序的比较，到底谁快-CSDN论坛，具体问题如下：
本网根据需求用户需求，为用户寻得以下其他网友提供的解决方法，方法仅供参考，具体如下：解决方案1：
4种非平方级的排序：
希尔排序，堆排序，归并排序，快速排序
我测试的平均排序时间：数据是随机整数，时间单位是秒
数据规模&&&&快速排序&&&&归并排序&&&&希尔排序&&&&堆排序
1000万&&&&&&&0.75&&&&&&&&&&&1.22&&&&&&&&&&1.77&&&&&&&&&&3.57
5000万&&&&&&&3.78&&&&&&&&&&&6.29&&&&&&&&&&9.48&&&&&&&&&26.54&&
1亿&&&&&&&&&&&&&7.65&&&&&&&&&&13.06&&&&&&&&18.79&&&&&&&&61.31
堆排序是最差的。
这是算法硬伤，没办法的。因为每次取一个最大值和堆底部的数据（记为X）交换，重新筛选堆，把堆顶的X调整到位，有很大可能是依旧调整到堆的底部（堆的底部X显然是比较小的数，才会在底部），然后再次和堆顶最大值交换，再调整下来。
从上面看出，堆排序做了许多无用功。
至于快速排序为啥比归并排序快，我说不清楚。
解决方案2：
算法复杂度一样只是说明随着数据量的增加，算法时间代价增长的趋势相同，并不是执行的时间就一样，这里面有很多常量参数的差别，即使是同样的算法，不同的人写的代码，不同的应用场景下执行时间也可能差别很大。
快排的最坏时间虽然复杂度高，但是在统计意义上，这种数据出现的概率极小，而堆排序过程里的交换跟快排过程里的交换虽然都是常量时间，但是常量时间差很多。
解决方案3：
引用&1&楼&ananluowei&的回复:4种非平方级的排序：
希尔排序，堆排序，归并排序，快速排序
我测试的平均排序时间：数据是随机整数，时间单位是秒
数据规模&&&&快速排序&&&&归并排序&&&&希尔排序&&&&堆排序
1000万&&&&&&&0.75&&&&&&&&&&&1.22&&&&&&&&&&1.77&&&&&&&&&&3.57
5000万&&&&&&&3.78&&&&&&&&&&&6.29&&&&&&&&&&9.48&&&&&&&&&26.54&&
1亿&&&&&&&&&&&&&7.65&&&&&&&&&&13.06&&&&&&&&18.79&&&&&&&&61.31
堆排序是最差的。
这是算法硬伤，没办法的。因为每次取一个最大值和堆底部的数据（记为X）交换，重新筛选堆，把堆顶的X调整到位，有很大可能是依旧调整到堆的底部（堆的底部X显然是比较小的数，才会在底部），然后再次和堆顶最大值交换，再调整下来。
从上面看出，堆排序做了许多无用功。
至于快速排序为啥比归并排序快，我说不清楚。
请问你的快快速排序是怎么写的，我写的快速排序，当测试数组大于5000的时候就栈溢出了。
其他的几个排序都对着，不过他们呢没有用栈。
这是快速排序的代码，win7&32位，vs2010.
int&FindPos(double&*p,int&low,int&high)
double&val&=&p[low];
while&(low&high)
while(low&high&&p[high]&=val)
p[low]=p[high];
while(low&high&&p[low]&val)
p[high]=p[low];
void&QuickSort(double&*a,int&low,int&high)
if&(!a||high&low)
if&(low&high)
int&pos=FindPos(a,low,high);
QuickSort(a,low,pos-1);
QuickSort(a,pos+1,high);
解决方案4：
引用&3&楼&cuijiyue&的回复:
哦，我这个快速排序小段区间用了插入排序优化，就算不用，也太会溢出啊，除非碰到特别设计的针对算法的数据序列。
template&&typename&T&
void&QuickSort(T&arr[],&int&n)&&&//快速排序
QSpartition(arr,&0,&n&-&1);
InsertSort(arr,&n);&&&&&&&&&&//最后用插入排序对整个数组排序
template&&typename&T&
void&QSpartition(T&arr[],&int&low,&int&high)&&&&&//快速排序递归函数
// if&(low&&=&high)&&&&&//有插入排序，不需要这句
const&int&min_insert&=&128;
if&(high&-&low&&&min_insert)&&//数据小于一定数量的时候用直接插入排序
&&//最后用插入排序对整个数组排序
&&&&//下面一段是前中后3个数据进行插入排序
i&=&(low&+&high)&/&2;
if&(arr[i]&&&arr[low])
temp&=&arr[i];
arr[i]&=&arr[low];
arr[low]&=&
if&(arr[high]&&&arr[i])
temp&=&arr[high];
arr[high]&=&arr[i];
if&(arr[i]&&&arr[low])
temp&=&arr[i];
arr[i]&=&arr[low];
arr[low]&=&
// if&(high&-&low&&&3)&&&//小区间用插入排序，这里就不需要判断了
&&&&&&&&&&&//不用插入排序，只有2个数据的时候排序错误
temp&=&arr[i];&&&&&&&&&&&
arr[i]&=&arr[low&+&1];&&//中值放在最左边
i&=&low&+&1;&&&&&&&&&&&&//左右边界缩小1
j&=&high&-&1;&&&&&&&&&&&//边界2个数字插入排序排过，满足左&=中&=右
while&(i&&&j)
while&(temp&&&arr[j]&&&&i&&&j)&&&//从右往左扫描小于目标的值，应该放在左半部分
if&(i&&&j)&&&&&&&&&&&&&&&&&&&&&&&&//找到后放在左边
arr[i++]&=&arr[j];
while&(temp&&&arr[i]&&&&i&&&j)&&&//从左往右扫描大于目标的值，要放在右边
arr[j--]&=&arr[i];
arr[i]&=&&&&&&&&&&&&&&&&&&&&&&&&//&i&=&j，正好是分界线，回填目标值
if&((i&-&low)&&&1)&
QSpartition(arr,&low,&i&-&1);&&&&&//递归左边
if&((high&-&i)&&&1)
QSpartition(arr,&i&+&1,&high);&&&&&//递归右边
template&&typename&T&
void&InsertSort(T&arr[],&int&n)&&&//直接插入排序
for&(i&=&1;&i&&&n;&i++)
temp&=&arr[i];
for&(j&=&i&-&1;&j&&=&0;&j--)
if&(temp&&&arr[j])&&&&&&&&&&&&//逐个往前比较，碰到大于目标的，拉过来
arr[j&+&1]&=&arr[j];
arr[j&+&1]&=&&&&&&&&&&&&&&&&//把目标值填入空位
解决方案5：
引用&4&楼&ananluowei&的回复:Quote: 引用&3&楼&cuijiyue&的回复:
哦，我这个快速排序小段区间用了插入排序优化，就算不用，也太会溢出啊，除非碰到特别设计的针对算法的数据序列。
template&&typename&T&
void&QuickSort(T&arr[],&int&n)&&&//快速排序
QSpartition(arr,&0,&n&-&1);
InsertSort(arr,&n);&&&&&&&&&&//最后用插入排序对整个数组排序
template&&typename&T&
void&QSpartition(T&arr[],&int&low,&int&high)&&&&&//快速排序递归函数
// if&(low&&=&high)&&&&&//有插入排序，不需要这句
const&int&min_insert&=&128;
if&(high&-&low&&&min_insert)&&//数据小于一定数量的时候用直接插入排序
&&//最后用插入排序对整个数组排序
&&&&//下面一段是前中后3个数据进行插入排序
i&=&(low&+&high)&/&2;
if&(arr[i]&&&arr[low])
temp&=&arr[i];
arr[i]&=&arr[low];
arr[low]&=&
if&(arr[high]&&&arr[i])
temp&=&arr[high];
arr[high]&=&arr[i];
if&(arr[i]&&&arr[low])
temp&=&arr[i];
arr[i]&=&arr[low];
arr[low]&=&
// if&(high&-&low&&&3)&&&//小区间用插入排序，这里就不需要判断了
&&&&&&&&&&&//不用插入排序，只有2个数据的时候排序错误
temp&=&arr[i];&&&&&&&&&&&
arr[i]&=&arr[low&+&1];&&//中值放在最左边
i&=&low&+&1;&&&&&&&&&&&&//左右边界缩小1
j&=&high&-&1;&&&&&&&&&&&//边界2个数字插入排序排过，满足左&=中&=右
while&(i&&&j)
while&(temp&&&arr[j]&&&&i&&&j)&&&//从右往左扫描小于目标的值，应该放在左半部分
if&(i&&&j)&&&&&&&&&&&&&&&&&&&&&&&&//找到后放在左边
arr[i++]&=&arr[j];
while&(temp&&&arr[i]&&&&i&&&j)&&&//从左往右扫描大于目标的值，要放在右边
arr[j--]&=&arr[i];
arr[i]&=&&&&&&&&&&&&&&&&&&&&&&&&//&i&=&j，正好是分界线，回填目标值
if&((i&-&low)&&&1)&
QSpartition(arr,&low,&i&-&1);&&&&&//递归左边
if&((high&-&i)&&&1)
QSpartition(arr,&i&+&1,&high);&&&&&//递归右边
template&&typename&T&
void&InsertSort(T&arr[],&int&n)&&&//直接插入排序
for&(i&=&1;&i&&&n;&i++)
temp&=&arr[i];
for&(j&=&i&-&1;&j&&=&0;&j--)
if&(temp&&&arr[j])&&&&&&&&&&&&//逐个往前比较，碰到大于目标的，拉过来
arr[j&+&1]&=&arr[j];
arr[j&+&1]&=&&&&&&&&&&&&&&&&//把目标值填入空位
多谢了，看你代码里主要有两个优化，我看的书是《大话数据结构》，那个比较低位、高位、中间位的优化叫选取枢轴，添上后代码确实不会栈溢出了，
加入插入排序的优化后，时间会比没有加之前缩短一倍。
解决方案6：
没事别递归，栈溢出
解决方案7：
谁说的快排好啊？我一般都用堆的，我认为堆好。
这个哪有谱啊，考察使用环境啊。不是只有时间代价一种衡量标准的，还有空间代价，LZ也有过栈溢出的经历，那不就是空间代价过高了嘛。改成别的办法还是避免不了空间代价。LZ自己不是也已经把空间待见列出来了嘛。
解决方案8：
引用&7&楼&zerglarva_aahha&的回复:谁说的快排好啊？我一般都用堆的，我认为堆好。
这个哪有谱啊，考察使用环境啊。不是只有时间代价一种衡量标准的，还有空间代价，LZ也有过栈溢出的经历，那不就是空间代价过高了嘛。改成别的办法还是避免不了空间代价。LZ自己不是也已经把空间待见列出来了嘛。
我是看讲解快速排序的时候说，快速排序之所以叫快速排序，就是因为它最快，才叫快速。然后后面总结的时候，列了张表，就是我贴出来的，然后我就深深的疑问了
解决方案9：
具体问题具体分析，快速排序当数据量越大的时候越能体现出它的优势。
解决方案10：
引用&1&楼&ananluowei&的回复:4种非平方级的排序：
希尔排序，堆排序，归并排序，快速排序
我测试的平均排序时间：数据是随机整数，时间单位是秒
数据规模&&&&快速排序&&&&归并排序&&&&希尔排序&&&&堆排序
1000万&&&&&&&0.75&&&&&&&&&&&1.22&&&&&&&&&&1.77&&&&&&&&&&3.57
5000万&&&&&&&3.78&&&&&&&&&&&6.29&&&&&&&&&&9.48&&&&&&&&&26.54&&
1亿&&&&&&&&&&&&&7.65&&&&&&&&&&13.06&&&&&&&&18.79&&&&&&&&61.31
堆排序是最差的。
这是算法硬伤，没办法的。因为每次取一个最大值和堆底部的数据（记为X）交换，重新筛选堆，把堆顶的X调整到位，有很大可能是依旧调整到堆的底部（堆的底部X显然是比较小的数，才会在底部），然后再次和堆顶最大值交换，再调整下来。
从上面看出，堆排序做了许多无用功。
至于快速排序为啥比归并排序快，我说不清楚。
堆排序为什么比希尔排序慢呢，难道你写错了?logN复杂度的“优先队列的pop”，一共执行N次，怎么着也比希尔排序的O(N^(5/4))要快啊。
解决方案11：
引用&10&楼&SmallYamateh&的回复:堆排序为什么比希尔排序慢呢，难道你写错了?logN复杂度的“优先队列的pop”，一共执行N次，怎么着也比希尔排序的O(N^(5/4))要快啊。
我自己按照堆排序的算法思想实现了堆排序，写完后对照网上的代码，代码几乎是差不多的。
至于为何堆排序效率比希尔排序慢很多，我在上面帖子已经说了，是堆排序的算法缺陷造成无用功太多。（我把堆排序看成是高级排序中的冒泡排序，冒泡也是两两交换做了太多无用功所以最慢。）
贴下我实现的希尔排序和堆排序，你可以自己去运行比较。
template&&typename&T&
void&ShellSort(T&arr[],&int&n)&&&&&&&&&&//希尔排序就是增量逐步缩小的直接插入排序
{&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&//这里采用黄金分割的比例逐次减小增量
int&gap&=&n&*&0.382&+&0.5;&&&&&&&&&&//所以代码和直接插入排序非常像。区别就是把增量1换成gap
while&(gap&&&0)
for&(i&=&&i&&&n;&i++)
temp&=&arr[i];
for&(j&=&i&-&&j&&=&0;&j&-=&gap)
if&(temp&&&arr[j])
arr[j&+&gap]&=&arr[j];
arr[j&+&gap]&=&
gap&=&gap&*&0.382&+&0.5;
template&&typename&T&
void&HeapSort(T&arr[],&int&n)
for&(int&i&=&n&/&2&-&1;&i&&=&0;&i--)&&&&//建立最大堆，从最后一个非叶节点开始
MaxHeapify(arr,&n,&i);&&&&&&&&&&&&&&//对于N规模的堆（0，n-1),&n/2-1是最后一个非叶节点
for&(int&i&=&n&-&1;&i&&&0;&i--)&&&
temp&=&arr[i];&&&&&&&&&&&&&&&//每次取堆顶数据和堆底部数据交换
arr[i]&=&arr[0];&&&&&&&&&&&&&//并逐步缩小堆的大小
MaxHeapify(arr,&i,&0);&&&&&&&//重新筛选堆
template&&typename&T&
void&MaxHeapify(T&arr[],&int&n,&int&i)
T&temp,&max_
int&pos&=&i;
int&left&=&pos&*&2&+&1;
int&right&=&left&+&1;
temp&=&arr[pos];
while&(left&&&n)&&&&&//至少有左子树
//取左右子树的最大值
max_data&=&arr[left];
max_pos&=&
if&(right&&&n)&&&//左右子树均有
if&(arr[right]&&&arr[left])
max_data&=&arr[right];
max_pos&=&
if&(temp&&&max_data)&&&&&&&&&//节点比左右子树最大值小，继续向下调整
arr[pos]&=&max_
pos&=&max_
left&=&pos&*&2&+&1;
right&=&left&+&1;
arr[pos]&=&&&&//回填
我觉得我写的堆排序中规中矩，没啥大问题啊。难道堆排序还有更强悍的实现方法？
解决方案12：
Mark一下,&有时间好好做一些实验，给出具体结果。
这里先说说的我的看法，希望实验能支持我的预测。
1.&快排的时间复杂度是不稳定的，在最快情况下比归并排序慢的多。
2.&当数据量大时，充分优化的归并排序可比快速排序更快。其原因有
&&1）.&归并排序对内存的访问是严格的顺序方式（3个2个源数组，1个目标数组，都是顺序放分），故cache的命中率比快排更高，从这点上，相同的内存读写操作，归并优于快排，当数组占用的空间大大超过cache的大小，则这一优势将更加明显。
&&2）普通写法的归并排序有2个缺点，如果改进，则可以提速。如果你的实验是基于最普通的版本，得到的结果是快排优于归并，而优化的归并排序的版本，其性能则可能反超快排。
&&2.1）&归并排序不是In&place.需要将结果存储到临时缓冲区，然后在复制回来，这个过程可以优化掉。使用乒乓做法，在第i级归并过程，从buff1&归并到buff2,在i+1级归并过程，从buff2复制到buff1。
&&2.2）&2路归并排序的核心动作是比较2个对列的头元素那个更大，其比较结果是随机的，2个分支机会均等，CPU的分支预测算法不起作用，当预测失败，可大大降低程序性能，如果消除这个分支，可明显提高程序性能。
解决方案13：
楼主知道标准库的sort是怎么实现的么？&先快排，递归深度超过一个阀值就改成堆排，然后对最后的几个进行插入排序。
解决方案14：
引用&12&楼&liangbch&的回复:Mark一下,&有时间好好做一些实验，给出具体结果。
这里先说说的我的看法，希望实验能支持我的预测。
1.&快排的时间复杂度是不稳定的，在最快情况下比归并排序慢的多。
2.&当数据量大时，充分优化的归并排序可比快速排序更快。其原因有
&&1）.&归并排序对内存的访问是严格的顺序方式（3个2个源数组，1个目标数组，都是顺序放分），故cache的命中率比快排更高，从这点上，相同的内存读写操作，归并优于快排，当数组占用的空间大大超过cache的大小，则这一优势将更加明显。
&&2）普通写法的归并排序有2个缺点，如果改进，则可以提速。如果你的实验是基于最普通的版本，得到的结果是快排优于归并，而优化的归并排序的版本，其性能则可能反超快排。
&&2.1）&归并排序不是In&place.需要将结果存储到临时缓冲区，然后在复制回来，这个过程可以优化掉。使用乒乓做法，在第i级归并过程，从buff1&归并到buff2,在i+1级归并过程，从buff2复制到buff1。
&&2.2）&2路归并排序的核心动作是比较2个对列的头元素那个更大，其比较结果是随机的，2个分支机会均等，CPU的分支预测算法不起作用，当预测失败，可大大降低程序性能，如果消除这个分支，可明显提高程序性能。
1.快排的时间复杂度确实不稳定，极端情况是O(n^2)，但是平摊下来是T(n*lg(n))，而归并是严格的O(n*log(n))。
2.快速排序比归并排序快。其原因有
&&1）快排对内存的访问是顺序方式（包括逆序），只有两个目标而且是同一个数组，故cache的命中率不会比归并低。特别是数组空间接近于cache大小时，这一优势将更加明显。
&&2）快排的内存写操作次数平摊下来是T(n*lg(n)/2)，而归并的内存写操作次数是严格的O(n*log(n))，由于内存写操作开销比较大，所以对于随机数据快排优于归并。
解决方案15：
快排比归并排序快的原因是快排对数组的访问次数要少于归并排序～
解决方案16：
同学们，这些算法都有标准的开源程序。
自己写程序对理解算法的确有好处。
但是如果用于得到一般性的比较结果，那是靠不住的。
解决方案17：
stl中的快速排序有很多优化，比如：随机算法，三数取中等几乎能够避免最坏情况发生。
本文相关：47被浏览9,475分享邀请回答122 条评论分享收藏感谢收起目录 & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &&
& & &1、本文介绍
& & &2、快速排序
& & &3、随机化快速排序
& & &4、完整源码
& & &5、参考资料
内容 & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &
& & &1、本文介绍 & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &&
& & & & & &主要内容分为两部分，一部分是介绍快速排序算法，分析其在最好、最坏以及最好最差交替出现情况下的算法效率；另一部分则是介绍随机化快排算法，以及分析其算法复杂度。最后给出c++实现代码。
& & &2、快速排序 & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &&
& & & & 快速排序也是基于分治思想，首先把要排序的数组分为两份，然后再分别对分好的子数组进行快速排序。当子数组为1个元素时递归介绍，排序完成。快速排序属于&原地排序&，就是说在原有的数组内存上排序、不占用其他内存。归并排序就不一样，它则需要额外的空间来进行归并排序操作。下图是快速排序的分治思想：
由上图可以知道，快速排序里面最关键的就是第一步：分化（Partition）的步骤，这是该算法处理问题的核心。所以我们可以把快排看成是递归地划分数组，就像归并排序是递归地合并数组一样。关于Paritition的具体算法，目前有好几种，其伪代码稍有不同但是它们的原理都是一样的。当然最重要的一点是分化（Partition）的算法复杂度都是线性的，也就是O(n)。下面是分化（Partition）的一种伪码：
1 Partition(A,p,q)
//选第一个为主元
//小于主元的数据放在左边
exch A[i] &-& A[j]
// 交换A[i]
exch A[p] &-& A[i]
//返回划分好后主元索引
分划好后就是简单的递归，下面是快排的伪代码：
1 QuickSort(A,p,q)
//不满足就介绍递归
r &- Partition(A,p,q) //分划
QuickSort(A，p , r-1) //递归快排左子数组
QuickSort(A , r+1 ,q)
//递归快排右子数组
& &接下来分析快排的算法效率
& & 1）最坏情况下分析
& & & & &当输入序列是正序或者是反序的时候，效率最坏，这时效率是&T(n2)
& & 2) &最优情况下分析
& & & &其他情况下的算法效率趋向于&T（nlgn）
& 那么我们如何保证我们总是效率处于最优情况下的呢？这就是随机化快速排序需要解决的问题。
& & &3、随机化快速排序 & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &
& & & &&我们已经知道，若输入本身已被排序，那么对于快排来说就糟了。那么如何避免这样的情况？一种方法时随机排列序列中的元素；另一种方法时随机地选择主元（pivot）。这便是随机化快速排序的思想，这种快排的好处是：其运行时间不依赖于输入序列的顺序。
& & & 经分析，&随机化快排的算法效率是&T(nlgn)。
& & 实现：我们只需在选取主元时加入随机因素即可。其他与快排一样
& & &下面是分化（Partition）编程（c++）实现
Random_Partition(vector&T& &A,int p,int q)
int i=rand()%(q-p)+p;
//此行与快排不同、加入随机数参数器
Swap(A[i],A[p]);
//此行与快排不同、随机选取主元
return Partition(A,p,q);//此次与快速排序一样
// 随机化快速排序1 void Random_Quick_Sort(vector&T& &A,int p,int q)
int i=Random_Partition(A,p,q);
Random_Quick_Sort(A,p,i-1);
Random_Quick_Sort(A,i+1,q);
& & &4、完整源码 & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &
& & & &下面源码包含之前讨论过的算法。最后给出时间比较
& & & CTimer.h &(测试间的头文件实现，不懂无需纠结)
1 #ifndef CTIMER_HH
2 #define CTIMER_HH
3 class CTimer
QueryPerformanceFrequency(&m_Frequency);
void Start()
QueryPerformanceCounter(&m_StartCount);
double End()
LARGE_INTEGER CurrentC
QueryPerformanceCounter(&CurrentCount);
return double(CurrentCount.LowPart - m_StartCount.LowPart) *1000/ (double)m_Frequency.LowP
void ShowNow()
LARGE_INTEGER CurrentC
QueryPerformanceCounter(&CurrentCount);
cout&&"Timer Count is:"&&double(CurrentCount.LowPart - m_StartCount.LowPart)*1000 / (double)m_Frequency.LowPart&&
27 private:
LARGE_INTEGER m_F
LARGE_INTEGER m_StartC
& & &Sort.h &(排序算法[插入排序、归并排序、快速排序、随机化快速排序]实现头文件)
1 #ifndef SORT_HH
2 #define SORT_HH
3 template&typename T &//带模板
4 class Sort
void insertion_sort(vector&T& &A);//插入排序
void merge_sort(vector&T& &A,int p,int r);//归并排序
void print_element(vector&T& A);//打印数组
void Quick_Sort(vector&T& &A,int p,int q);//快速排序
int Partition(vector&T& &A,int p,int q);//分划
void Swap(T &m,T &n);//交换数据
void Random_Quick_Sort(vector&T& &A,int p,int q);//随机化快速排序
int Random_Partition(vector&T& &A,int p,int q);//随机化分划
void merge(vector&T& &A,int p,int q,int r);// 归并排序子程序
18 template&typename T&//插入排序
19 void Sort&T&::insertion_sort(vector&T& &A)
int len=A.size();
for (j=1;j&j++)
while (i&=0&&A[i]&key)
A[i+1]=A[i];
37 template&typename T&// 归并排序子程序
38 void Sort&T&::merge(vector&T& &A,int p,int q,int r)
int n1=q-p+1;
int n2=r-q;
T *L=new T[n1+1];
T *R=new T[n2+1];
for (int i=0;i&n1;i++)
L[i]=A[i+p];
for (int i=0;i&n2;i++)
R[i]=A[i+q+1];
L[n1]=R[n2]=INT_MAX;
int i=0,j=0;
for (int k=p;k&=r;k++)
if (L[i]&R[j])
A[k]=R[j];
A[k]=L[i];
delete[] L;
delete[] R;
72 template&typename T&//归并排序
73 void Sort&T&::merge_sort(vector&T& &A,int p,int r)
int mid=(p+r)/2;
merge_sort(A,p,mid);
merge_sort(A,mid+1,r);
merge(A,p,mid,r);
84 template&typename T&//交换数据
85 void Sort&T&::Swap(T &m,T &n)
93 /***********快速排序分划程序*************/
94 template&typename T&
95 int Sort&T&::Partition(vector&T& &A,int p,int q)
for (int j=p+1;j&=q;j++)
if (A[j]&x)
Swap(A[i],A[j]);
Swap(A[p],A[i]);
110 template&typename T&//快速排序
111 void Sort&T&::Quick_Sort(vector&T& &A,int p,int q)
int i=Partition(A,p,q);
Quick_Sort(A,p,i-1);
Quick_Sort(A,i+1,q);
121 template&typename T&//随机化快速排序分划程序
122 int Sort&T&::Random_Partition(vector&T& &A,int p,int q)
int i=rand()%(q-p)+p;
Swap(A[i],A[p]);
return Partition(A,p,q);
129 template&typename T&//随机化快速排序
130 void Sort&T&::Random_Quick_Sort(vector&T& &A,int p,int q)
int i=Random_Partition(A,p,q);
Random_Quick_Sort(A,p,i-1);
Random_Quick_Sort(A,i+1,q);
140 template&typename T&//打印数组
141 void Sort&T&::print_element(vector&T& A)
int len=A.size();
for (int i=0;i&i++)
std::cout&&A[i]&&" ";
std::cout&&std::
150 #endif
Sort_main.cpp （测试主程序）
1 #include &iostream&
2 #include &vector&
3 #include &time.h&
4 #include &Windows.h&
5 using namespace
6 #include "Sort.h"
7 #include "CTimer.h"
//排序数组大小
10 // 随机参数排序数组
11 void Random(vector&int& &a,int n)
srand( (unsigned)time( NULL ) );
while(i&n)
a[i++]=rand();
20 int main()
Sort&int& sort1;
vector&int & vec_int(N);
Random(vec_int,N);
cout&&"源数组：";
sort1.print_element(vec_int);
t.Start();
sort1.Quick_Sort(vec_int,0,vec_int.size()-1);
cout&&"快速排序:"&&t.End()&&"ms"&&
sort1.print_element(vec_int);
Random(vec_int,N);
t.Start();
sort1.Random_Quick_Sort(vec_int,0,vec_int.size()-1);
cout&&"随机化快速排序:"&&t.End()&&"ms"&&
sort1.print_element(vec_int);
Random(vec_int,N);
t.Start();
sort1.insertion_sort(vec_int);
cout&&"插入排序:"&&t.End()&&"ms"&&
sort1.print_element(vec_int);
Random(vec_int,N);
t.Start();
sort1.merge_sort(vec_int,0,vec_int.size()-1);
cout&&"归并排序:"&&t.End()&&"ms"&&
sort1.print_element(vec_int);
system("PAUSE");
排序算法时间比较：
快速排序（ms）
随机化快速排序(ms)
插入排序（ms）
归并排序(ms)
......（太大、没测）
自我小结：对随机产生的数组进行排序，1）可以发现插入排序没有优势、特别是数组比较大时耗时太多；2）快速排序、随机化快速排序、归并排序性能不错，然而两种快排比归并排序性能好点；3）当数据量变大时，可以看出性能排序为快速排序、随机化快速排序、归并排序、插入排序；4）由于这里的数组是由随机数产生的，没有显示出随机化快速排序的优势，但是当数组为已排序情况下随机化快排将比快排性能好。
& & &5、参考资料 & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &&
& & & 【1】
& & & 【2】
& & & 【3】
阅读(...) 评论()