排序算法比较研究-600-源码+说明资料

更多请下载演示查看

一、 排序算法比较研究（基本题目）

【问题描述】在教科书中，各种排序算法的时间复杂度分析结果只给出了算法执行时间的渐进度，或者大概执行时间。试通过随机数据比较算法的关键字比较次数和关键字移动次数，以取得直观的感受。

【基本要求】（1）对各种内部排序算法进行比较，包括（书中没有提到请自行查阅课外资料）：冒泡排序，插入排序，选择排序，计数排序，快速排序，归并排序，希尔排序，基数排序，堆排序。

（2）待排序表的表长不小于100；其中数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标有关键字参加的比较次数和关键字的移动次数。（关键字交换计为3次移动）

（3）最后要对结果作出简单的分析，包括对各组数据得出结果波动大小的解释。

【实现提示】主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性，如：正序，逆序和不同程度的乱序。注意采用分块调试的方法。

一、需求分析
对各种内部排序算法进行比较，包括（书中没有提到请自行查阅课外资料）：冒泡排序，插入排序，选择排序，计数排序，快速排序，归并排序，希尔排序，基数排序，堆排序。
待排序表的表长不小于100；其中数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标有关键字参加的比较次数和关键字的移动次数。（关键字交换计为3次移动）
最后要对结果作出简单的分析，包括对各组数据得出结果波动大小的解释。
1．冒泡排序：依次比较相邻的两个数，将大数放在前面，小数放在后面。即首先比较第1个和第2个数，将大数放前，小数放后。然后比较第2个数和第3个数，将大数放前，小数放后，如此继续，直至比较最后两个数，将大数放前，小数放后，此时第一趟结束，在最后的数必是所有数中的最小数。重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再大于第2个数），将大数放前，小数放后，一直比较到最小数前的一对相邻数，将大数放前，小数放后，第二趟结束，在倒数第二个数中得到一个新的最小数。如此下去，直至最终完成排序。
2．插入算法:有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为⊙(㎡)。是稳定的排序方法。插入算法（insertion sort）把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，再把这个最后元素插入到此刻已是有序的第一部分里的正确位置中。
3．选择排序:每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。　　选择排序是不稳定的排序方法。　　n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：　　①初始状态：无序区为R[1..n]，有序区为空。　　②第1趟排序　　在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。　　……　　③第i趟排序　　第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。　　这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
4．计数排序:利用元素的实际值来确定它们在输出数组中的位置。因此，计数排序算法不是一个基于比较的排序算法，从而它的计算时间下界不再是Ω(nlogn)。另一方面，计数排序算法之所以能取得线性计算时间的上界是因为对元素的取值范围作了一定限制，即k=O(n)。如果k=n2,n3,..，就得不到线性时间的上界。此外，我们还看到，由于算法第4行使用了downto语句，经计数排序，输出序列中值相同的元素之间的相对次序与他们在输入序列中的相对次序相同，换句话说，计数排序算法是一个稳定的排序算法。
5．快速排序(Quick Sort)是一种有效的排序算法。虽然算法在最坏的情况下运行时间为O(n^2)，但由于平均运行时间为O(nlogn)，并且在内存使用、程序实现复杂性上表现优秀，尤其是对快速排序算法进行随机化的可能，使得快速排序在一般情况下是最实用的排序方法之一。　　快速排序被认为是当前最优秀的内部排序方法。
6．归并排序:是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要.这也是它比快速排序优势的地方.
7．希尔排序:先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
8．基数排序:则是属于“分配式排序”（distribution sort），基数排序法又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。
9．堆排序:是一树形选择排序。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构)，在当前无序区中选择关键字最大(或最小)的记录。