排序算法综合实验
作者：
一、实验目的
通过上机来体验和掌握课本的有关基本知识，加深对排序算法的认识。
二、实验要求
1．实现基本排序方法：直接插入、希尔、直接选择、冒泡、快速、堆、二路归并； 2．每种基本排序方法尽量给出多种实现（包括改进）； 3．给出实验结果：
445
（1）随机生成若干个随机数进行排序（如n＝10，2＊10，10，?等），记录每个排序的时间耗费（绝对时间？逻辑时间（关键字比较次数，移动次数）？）。
4
（2）分别给出正序和反序的初始序列进行排序（如n＝10），检验算法对初始序列的敏感程度。
（3）给出实验结果、原因分析、结论等（如改进效果明显或不明显的原因？算法的实际时间增长速度如何？复杂性相当的算法之间快慢如何？等等）。 （4）所有实验结果汇集成一张表。
三、几种排序算法
1、直接插入排序 1.1原理
在排序过程中，每次都将无序区中第1条记录插入到有序区中适当位置，使其仍保持有序。初始时，取第1条记录为有序区，其他记录为无序区。随着排序过程的进行，有序区不断扩大，无序区不断缩小。最终无序区为空，有序区包含了全部记录，排序结束。
1.2算法
1.2.1带监视哨
//直接插入排序，带监视哨(并不改变关键字次数) void InsertSort1(list R,int n) { int i,j;
for(i=2;i<=n;i++) { //依次插入R[2],R[3],?,R[n] if(CPP,R[i].key>=R[i-1].key) continue;
//R[i]大于有序区最后一个记录，则本趟不需插入 MPP,R[0]=R[i]; //R[0]是监视哨 j=i-1;
do { //查找R[i]的插入位置 MPP,R[j+1]=R[j];j--; //记录后移，继续向前搜索 } while(CPP,R[0].key MPP,R[j+1]=R[0]; //插入R[i] } } 1.2.2无监视哨 //直接插入排序，无监视哨 void InsertSort2(list R,int n) { int i,j;rectype x; //x为辅助量(用R[0]代替时间变长) for(i=2;i<=n;i++) { //进行n-1次插入 if(CPP,R[i].key>=R[i-1].key) continue; MPP,x=R[i]; //待排记录暂存到x j=i-1; do { //顺序比较和移动 MPP,R[j+1]=R[j];j--; } while(j>=1 && (CPP,x.key 1.2.3改进：在查找插入位置时采用二分查找，即二分插入排序 void InsertSort3(list R，int n){ int i，j，low，high，mid; for(i=2;i<=n;i++){ //依次插入R[2]，R[3]，...，R[n] if(CPP，R[i].key>=R[i-1].key) continue; //R[i]大于有序区最后一个记录，不需插入 MPP，R[0]=R[i]; low=1;high=i-1; while(low<=high){ //查找R[i]的插入位置 mid=(low+high)/2; if(CPP，R[0].key 2、希尔排序 2.1原理 将数据表分成若干组，所有相隔为某个“增量”的记录为一组，在各组内进行直接插入排序；初始时增量d1较大，分组较多（每组的记录数少），以后增量逐渐减少，分组减少（每组的记录数增多），直到最后增量为1（d1>d2>...>dt=1），所有记录为同一组，再整体进行一次直接插入排序。 2.2算法 void ShellSort(list R，int n){ int h，i，j，k; for(h=n/2;h>=1;h=h/2){ for(i=1;i<=h;i++){ //i为组号 for(j=i+h;j<=n;j+=h){ //每组从第2个记录开始插入 if(CPP，R[j].key>=R[j-h].key) continue; //R[j]大于有序区最后一个记录， 则不需要插入 MPP，R[0]=R[j]; //R[0]保存待插入记录，但不是监视哨 k=j-h; //待插记录的前一个记录 do{ //查找正确的插入位置 MPP，R[k+h]=R[k];k=k-h; //后移记录，继续向前搜索 }while(k>0 && (CPP，R[0].key 3、直接选择排序 3.1原理 首先，所有记录组成初始无序区R[1]~R[n]，从中选出最小的记录，与无序区第一个记录R[1]交换；新的无序区为R[2]~R[n]，从中再选出最小的记录，与无序区第一个记录R[2]交换；类似，第i趟排序时R[1]~R[i-1]是有序区，无序区为R[i]~R[n]，从中选出最小的记录，将它与无序区第一个记录R[i]交换，R[1]~R[i]为新的有序区。因为没糖排序都使有序区中增加一个记录，所以，进行n-1趟排序后，整个数据表就全部有序了。 3.2算法 void SelectSort(list R，int n){ int i，j，k; for(i=1;i<=n-1;i++){ //n-1趟排序 k=i; for(j=i+1;j<=n;j++) //在当前无序区中找最小的记录R[k] if(R[j].key<=R[k].key) CPP， k=j; if(k!=i) {MP3， R[0]=R[i];R[i]=R[k];R[k]=R[0];} //交换R[i]和R[k]，R[0]作辅助 } } 4、冒泡排序 4.1原理 设想数据表R[1]~R[n]垂直放置，将每个记录R[i]看作是重量为R[i].key的气泡；根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡违反本原则的轻气泡，就使其向上“漂浮”，如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。 4.2算法 4.2.1上升法 void BubbleSort1(list R，int n) { int i，j，flag;rectype x; //x为辅助量(可用R[0]代替) for(i=1;i<=n-1;i++) { //做n-1趟扫描 flag=0; //置未交换标志 for(j=n;j>=i+1;j--) //从下向上扫描 if(CPP，R[j].key MP3，x=R[j];R[j]=R[j-1];R[j-1]=x;//交换 } if(!flag) break; //本趟未交换过记录，排序结束 } } 4.2.2下沉法 void BubbleSort2(list R，int n) { int i，j，flag;rectype x; //x为辅助量(可用R[0]代替) for(i=1;i<=n-1;i++) { //做n-1趟扫描 flag=0; //置未交换标志 for(j=1;j<=n-i;j++) //从上向下扫描 if(CPP，R[j].key>R[j+1].key) {//交换记录 flag=1; MP3，x=R[j];R[j]=R[j+1];R[j+1]=x;//交换 } if(!flag) break; //本趟未交换过记录，排序结束 } } 4.3.3改进：双向冒泡排序，每趟排序同时使轻气泡向上“漂浮”，重气泡向下“漂浮” void BubbleSort3(list R，int n){//双向冒泡排序 int i，j，k，flag;rectype x; i=1;j=n; while(i } 5、快速排序 5.1原理 在数据表中任取一个作为“基准”，将其余记录分为两组，第一组找那个个记录均小于或等于基准，第二组中个记录均大于或等于基准，而基准就排在这两组中间（这也是该记录的最终位置），这称为一趟快速排序（或一次划分）。对所分的两组记录分别重复上述方法，直到每组只有1个记录为止。 5.2算法 5.2.1一趟划分算法 int Partition(list R，int p，int q) {//对R[p]到R[q]划分，返回基准位置 int i，j;rectype x; //辅助量(可用R[0]代替) i=p;j=q;MPP，x=R[p]; //x存基准(无序区第一个记录) do { while((CPP，R[j].key>=x.key) && i while((CPP，R[i].key<=x.key) && i MPP，R[i]=x; //基准移到最终位置 return i; //最后i=j } 5.2.2主算法 void QuickSort1(list R，int s，int t) { int i; if(s>=t) return; //只有一个记录或无记录时无需排序 i=Partition(R，s，t); //对R[s]到R[t]做划分 QuickSort1(R，s，i-1); //递归处理左区间 QuickSort1(R，i+1，t); //递归处理右区间 } 6、堆排序 6.1原理 将待排序的记录序列建成一个堆，并借助于堆的性质进行的排序方法就是堆排序。它的原理：将原始的n个记录序列建成一个大根堆，称为初始堆，然后将它的根和最后的元素交换，除此之外的n-1个记录序列再重复上面的操作，直到记录序列为一个递增的序列。因此，堆排序的操作分为建立初始堆和用堆进行排序两步操作。 6.2算法 6.2.1建立初始堆算法