排序算法性能之比较
----19090107 李萍
✧课程题目：
编程实现希尔、快速、堆排序、归并排序算法。
要求随机产生待排数据存入磁盘文件，然后读入数据文件，实施排序后将数据写入另一个文件。
✧开发平台：
✧算法描述：
◆希尔排序：
希尔排序(Shell Sort)是对直接插入排序的一种改进，其基本思想为：先将整个待排序列划分成若干子序列，在子序列内分别进行直接插入排序，然后重复上述的分组和排序；只是分组方法不同；最后对整个序列进行直接插入排序。
◆快速排序：
快速排序几乎是最快的排序算法，被称为20世纪十大算法之一。
其基本思想为：从待排序记录序列中选取一个记录(通常选取第一个记录为枢轴)，其关键字值设为k，将关键字值小于k的记录移到前面，而将关键字值大于k的记录移到后面，结果将待排序记录序列分成两个子表，最后将关键字值为k的记录插入到分界线处。
这是一次“划分”。
对划分后的子表继续按上述原则进行划分，直到所有子表的表长不超过1为止，此时待排序记录序列就变成了一个有序序列。
◆堆排序：
堆排序是选择排序的一种改进。
堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左、右孩子结点的值(小顶堆)；或者每个结点都大于或等于其左、右孩子的值(大顶堆)。
堆排序基本思想为(采用大顶堆)：首先待排序的记录序列构造成一个堆，此时选出堆中所有记录的最大者，即堆顶记录，然后将它从堆中移走(通常将堆顶记录和堆中最后一个记录交换)，并将剩余的记录再调整成堆，这样又找出了次大的记录，依此类推，直到堆中只有一个记录为止。
◆归并排序：
归并就是将两个或两个以上的有序序列合并成一个有序序列。
归并排序的主要思想是：将若干有序序列逐步归并，最终归并为一个有序序列。
✧程序结构：
①各函数之间的关系图如下：
②程序运行结果：
欢迎界面：
运行界面：
✧算法性能比较
◆理论分析：
排序方法平均情况最好情况最坏情况
希尔排序O(nlog2n)~O(n2) O(n1.3) O(n2)
快速排序O(nlog2n) O(nlog2n) O(n2)
归并排序O(nlog2n) O(nlog2n) O(nlog2n)
堆排序O(nlog2n) O(nlog2n) O(nlog2n)
从时间复杂性上看：快速排序，归并排序和堆排序的平均复杂性相同，希尔排序的时间较大些。
◆实际分析：
在保证算法正确性的情况下，程序分别选取了
50000,100000,150000,200000,250000,300000,400000,500000,1000000,2000000个随机数，测试四种算法运行时间。
从测试结果上看：
1)当随机数个数在1000000以下时，四种算法的运行时间都在1s以下。
2)从图中可以很直观的看出快速排序至始至终都是运行速度最快的，性能最高。
3)当随机数个数在500000以下时，四种算法运行时间相差不大，随着随机数个数不断增大时，四种算法的效率可以明显看出来：快速排序>归并排序>堆排序>希尔排序。
4)堆排序和归并排序的运行时间相当，这和理论情况是相同的，但是快速排序却明显高于堆排序和归并排序，和理论情况有些出入。
希尔排序运行时间最长也是符合理论情况的。
◆原因分析：
为什么会出现理论结果与实际结果不符的情况呢？这里涉及两个概念：
1．时间频度：一个算法中的语句执行次数称为语句频度或时间频度。
代表一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道，记为T(n)。
2．时间复杂性：在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。
但有时我们想知道它变化时呈现什么规律。
为此，我们引入时间复杂度概念。
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。
记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与
T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。
所以时间复杂性只是在数量级上给用户提供一个时间的上下限，不是精准的运行时间，所以出现以上情况是正常的。
✧收获与体会
1)随机数的产生：
密码被广泛应用于信息系统中，以实现系统信息的保密性、完整性、可用性、可控性和不可否认性。
随机数在密码学中扮演着极其重要的角色，比如密钥管理、密码学协议、数字签名、身份认证等都需要用到随机数。
如何产生高质量的随机数一直是一个经久不衰的话题，如今，它已成为密码学乃至信息安全领域的一个重要研究方向。
生成随机数的方法繁多，从产生机理来说，可分为数学方法和物理方法两种，其所产生的随机数分别被称之为伪随机数和真随机数，前者易被破解，后者取自物理世界的真实随机源，难以破解，但这并不代表基于真随机源产生的随机数质量就很高，要取决于产生算法如何利用这个真随机源，相反的，许多用数学方法产生的随机数质量比较好。
因此，若能将数学方法和物理方法结合起来，则可能产生高质量的真随机数。
从实现方法来说，有以软件为主、以硬件为主以及软硬结合等方法。
设计一个真随机数发生器包括两步：首先是获取真随机源；然后是利用真随机源依照特定的数学方法获得真随机数。
【注1】
我们平时设计的小程序会涉及到随机数的产生，我们都会使用random函数，但单单使用此函数生成的随机数就是伪随机，每次产生的随机数都是相同的。
这是因为计算机产生随机数的方式一般是利用主板上的定时器产生的数据来生成的，而且会采用一定的算法，当一个数确定后，其实它的下一个数就确定了，所以每次都用相同的时间种子时，产生的随机数都是相同的。
因此，要想使每次的随机数都不同时，我们可以给予不同的时间种子，即在调用random函数之前先调用srand(time(NULL))。
2)测试程序运行时间函数的总结：
1．利用clock函数：
#include<iostream>
#include<ctime>
using namespace std;
int main()
{
time_t begin,end;
begin=clock();
//your code
end=clock();
cout<<"runtime: "<<double(end-begin)<<endl;
}【注2】
2．要进一步提高计时精度，就要采用QueryPerformanceFrequency()函数和QueryPerformanceCounter()函数。
2）这两个函数是VC提供的仅供Windows 9X使用的高精度时间函数，并要求计算机从硬件上支持高精度计时器。
int main(void)
{
LARGE_INTEGER BegainTime ;
LARGE_INTEGER EndTime ;
LARGE_INTEGER Frequency ;
QueryPerformanceFrequency(&Frequency);
QueryPerformanceCounter(&BegainTime) ;
//要测试的代码放在这里
QueryPerformanceCounter(&EndTime);
//输出运行时间（单位：s）
cout << "运行时间（单位：s）：" <<
(double)( EndTime.QuadPart -BegainTime.QuadPart )/ Frequency.QuadPart <<endl;
system("pause") ;
return 0 ;
} 【注3】
参考文献：
【1】吉根林、陈波数据结构教程(C++版) 电子工业出版社2009年
【2】宋勇、陈贤富、姚海东随机数发生器探讨及一种真随机数发生器实现
计算机工程2007,33(2)
- 5 -。