数据结构排序算法综合试验

本文格式为Word版，下载可任意编辑——数据结构排序算法综合试验排序算法综合试验

：

一、试验目的

通过上机来体验和把握课本的有关基本知识，加深对排序算法的认识。

二、试验要求

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带监视哨

//直接插入排序，带监视哨(并不改变关键字次数)voidInsertSort1(listR,intn){inti,j;

for(i=2;i=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=R[i-1].key)continue;

MPP,x=R[i];//待排记录暂存到xj=i-1;

do{//顺序比较和移动MPP,R[j+1]=R[j];j--;

}while(j>=1MPP,R[j+1]=x;//插入R[i]}}

1.2.3改进：在查找插入位置时采用二分查找，即二分插入排序voidInsertSort3(listR，intn){inti，j，low，high，mid;for(i=2;i=R[i-1].key)continue;//R[i]大于有序区最终一个记录，不需插入MPP，R[0]=R[i];low=1;high=i-1;while(low=high+1;j--)MPP，R[j+1]=R[j];//记录后移MPP，R[high+1]=R[0];}}

2、希尔排序2.1原理

将数据表分成若干组，所有相隔为某个“增量〞的记录为一组，在各组内进行直接插入排序；初始时增量d1较大，分组较多（每组的记录数少），以后增量逐渐减少，分组减少（每组的记录数增多），直到最终增量为1（d1>d2>...>dt=1），所有记录为同一组，再整体进行一次直接插入排序。

2.2算法

voidShellSort(listR，intn){inth，i，j，k;for(h=n/2;h>=1;h=h/2){for(i=1;i=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>0MPP，R[k+h]=R[0];//插入R[j]}}if(h==1)break;}}

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算法

voidSelectSort(listR，intn){inti，j，k;for(i=1;i=i+1;j--)//从下向上扫描

if(CPP，R[j].keyR[j+1].key){//交换记录flag=1;

MP3，x=R[j];R[j]=R[j+1];R[j+1]=x;//交换}

if(!flag)break;//本趟未交换过记录，排序终止}}

4.3.3改进：双向冒泡排序，每趟排序同时使轻气泡向上“漂泊〞，重气泡向下“漂泊〞voidBubbleSort3(listR，intn){//双向冒泡排序inti，j，k，flag;rectypex;i=1;j=n;while(i=i+1;k--)//从下向上扫描if(CPP，R[k].keyR[k+1].key){//交换记录flag=1;MP3，x=R[k];R[k]=R[k+1];R[k+1]=x;}if(!flag)break;j--;}

}

5、快速排序5.1原理

在数据表中任取一个作为“基准〞，将其余记录分为两组，第一组找那个个记录均小于或等于基准，其次组中个记录均大于或等于基准，而基准就排在这两组中间（这也是该记录的最终位置），这称为一趟快速排序（或一次划分）。对所分的两组记录分别重复上述方法，直到每组只有1个记录为止。

5.2算法

5.2.1一趟划分算法

intPartition(listR，intp，intq){//对R[p]到R[q]划分，返回基准位置inti，j;rectypex;//辅助量(可用R[0]代替)

i=p;j=q;MPP，x=R[p];//x存基准(无序区第一个记录)do{

while((CPP，R[j].key>=x.key)//从右向左扫描(取消=变快)if(i=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建立初始堆算法

非递归算法

voidSift1(listR，intp，intq)//堆范围为R[p]~R[q]，调整R[p]为堆{intj;

MPP，R[0]=R[p];//R[0]作辅助量j=2*p;while(j=R[j].key)break;//跟结点键值大于孩子结点，已经是堆，调整终止MPP，R[p]=R[j];//将R[j]换到双亲位置上p=j;//修改当前被调整结点j=2*p;//j指向R[p]的左孩子}MPP，R[p]=R[0];}

递归算法

voidSift2(listR，intp，intq)//堆范围为R[p]~R[q]，调整R[p]为堆{intj;if(p>=q)return;//只有一个元素j=2*p;if(j>q)return;if(j=R[j].key)return;//根结点关键字已最大MPP，R[0]=R[j];//交换R[j]和R[p]，R[0]作辅助量MPP，R[j]=R[p];MPP，R[p]=R[0];Sift2(R，j，q);}

6.2.2堆排序算法

voidHeapSort(listR，intn)//堆排序主程序{inti;for(i=n/2;i>=1;i--)Sift1(R，i，n);//建初始堆for(i=n;i>=2;i--){//进行n-1趟堆排序MPP，R[0]=R[1];//堆顶和当前堆底交换，R[0]作辅助量MPP，R[1]=R[i];MPP，R[i]=R[0];Sift1(R，1，i-1);}

7、二路归并排序7.1原理

将待排序记录R[0]到R[n-1]看成n个长度为1的有序子序列区，从第一个子序列开始，

把相邻的子序列两两归并，便得到[n/2]（取整数）个长度为2或1有序的子序列。然后再把这[n/2]个有序的子序列利用上面的方法两两归并，如此反复，直到最终得到一个长度为n的有序序列。

7.2算法

7.2.1一趟归并算法

voidMerge(listR，listR1，intlow，intmid，inthigh){

//合并R的两个子表：R[low]~R[mid]、R[mid+1]~R[high]，结果在R1中inti，j，k;i=low;j=mid+1;k=low;

while(i#include#include#include

#defineCPPC++#defineMPPM++#defineMP2M+=2#defineMP3M+=3

constintd=3;constintr=10;

constintmaxsize=100000;//数据表容量typedefintdatatype;typedefstruct{intf,e;}queue;

typedefstruct{

datatypekey;//关键字域datatypekey1[d];intnext;

}rectype;//记录类型

typedefrectypelist[maxsize+2];//数据表类型，0号单元不用

__int64C,M;//比较和移动次数

voidcheck(listR,intn){//检验排序结果inti;

for(i=2;i=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=R[i-1].key)continue;

MPP,x=R[i];//待排记录暂存到xj=i-1;

do{//顺序比较和移动MPP,R[j+1]=R[j];j--;

}while(j>=1MPP,R[j+1]=x;//插入R[i]}}

voidShellInsert(listR,intn,inth){inti,j,k;for(i=1;i=R[j-h].key)continue;MPP,R[0]=R[j];k=j-h;

do{MPP,R[k+h]=R[k];k=k-h;}while(CPP,k>0MPP,R[k+h]=R[0];}}

voidShellSort(listR,intn)//希尔排序{inth=n/2;while(h>=1)//各趟插入排序{ShellInsert(R,n,h);h=h/2;//缩小增量}}

//上升法冒泡排序

voidBubbleSort1(listR,intn){

inti,j,flag;rectypex;//x为辅助量(可用R[0]代替)for(i=1;i=i+1;j--)//从下向上扫描if(CPP,R[j].keyR[j+1].key){//交换记录flag=1;

MP3,x=R[j];R[j]=R[j+1];R[j+1]=x;//交换}

if(!flag)break;//本趟未交换过记录，排序终止}}

//快速排序，递归算法

intPartition(listR,intp,intq){//对R[p]到R[q]划分，返回基准位置inti,j;rectypex;//辅助量(可用R[0]代替)

i=p;j=q;MPP,x=R[p];//x存基准(无序区第一个记录)do{

while((CPP,R[j].key>=x.key)//从右向左扫描(取消=变快)if(i=t)return;//只有一个记录或无记录时无需排序i=Partition(R,s,t);//对R[s]到R[t]做划分QuickSort1(R,s,i-1);//递归处理左区间QuickSort1(R,i+1,t);//递归处理右区间}

//归并排序

voidMerge(listR,listR1,intlow,intmid,inthigh){

//合并R的两个子表：R[low]~R[mid]、R[mid+1]~R[high]，结果在R1中inti,j,k;i=low;j=mid+1;k=low;

while(i=R[j].key)break;R[i]=R[j];i=j;j=2*i;}R[i]=R[0];}

voidHeapSort(listR,intn)//堆排序主程序{inti;for(i=n/2;i>=1;i--)Sift(R,i,n);for(i=n;i>=2;i--){MP3,R[0]=R[1];R[1]=R[i];R[i]=R[0];Sift(R,1,i-1);}}

//选择排序

voidSelectSort(listR,intn){inti,j,k;for(i=1;i=0)x=x1;elsex=x1+M;returnx;}

intmain(){

rectype*R,*R1,*S;//R1用于归并排序的辅助存储，S用于保存初始排序数据R=newlist;if(R==NULL){cout>choice;switch(choice){case11:

t1=clock();

InsertSort1(R,n);t2=clock();break;case12:

t1=clock();

InsertSort2(R,n);t2=clock();break;case21:

\\n\\\\n\\\\n\\\\n\\\\n\\\\n\\\\n\\\\n\t1=clock();

BubbleSort1(R,n);t2=clock();break;case22:

t1=clock();

BubbleSort2(R,n);t2=clock();break;case31:

t1=clock();

QuickSort1(R,1,n);t2=clock();break;case41:

t1=clock();

MergeSort(R,R1,n);t2=clock();break;case51:

t1=clock();HeapSort(R,n);t2=clock();break;case61:

t1=clock();

SelectSort(R,n);t2=clock();break;case71:

t1=clock();ShellSort(R,n);t2=clock();break;default:;}

check(R,n);//disp(R,n);

cout

五、试验结果与分析

1、试验结：

试验数据结果汇总表：

CPU内存主板AMDA6-3420MAPUwithRadeon(tm)HDGraphics四核姓名李宇7.48GB华硕K53TK学号202331190310班级电信4班电mailliandyu2023@163.com操作系统Windows8专业版(Build9200),64-bit编译软C-free5.0件10^42*10^410^52*10^510^62*10^610^72*10^10^810^57正序逆序24.87100.12500.C4583直接插入40.99(带监视哨）t(时间)0.4041.665324.87100.12500.C4583直接插入40.46(无监视哨）t0.3881.586849.99199.94999.冒泡（上C058594升）129.1t1.2555.0884549.99199.94999.C04678128.6冒泡（下降）t1.2465.198710.1700.3662速（递归）9995.6166.4329995.6166.07519999.9517.74119999.9>5min>5min>5min堆排序(非递归)二路归并Ct选择排序C522.9>5min4.79625.8157.66320.8647.446256865411.250.0030.0070.0390.0830.460.9955.50210.1230.2671.5663.33318.7139.43224.0468.06836151.056619020614.090.0030.0080.0490.0990.5071.1846.45640.0290.0590.2990.599997997997997000015.1033.630.0040.010.0690.1370.9472.189840.0770.1681.0102.15588222.4t63>5min9.71071.01167.91089.2471.C048731573828.8565.22希尔排序t0.0050.0140.1090.2441.824.24344当数据表容量为10^8时系统出现问题。524506555.620.5132.05940.2660.6084.3417116765

2、试验分析2.1直接插入排序该算法虽然简单，但效率不高。由汇总表的数据可以看出，若初始数据为正序，总的关键字比较次数为最小，并且总的移动次数为0；若初始数据为逆序，总的比较次数达到最大值O（n2）；所以，算法对初始序列的敏感程度很大。由于该算法的时间繁杂度为O（n2），所以其对大规模的数据排序的效率很低，改进后的二分插入算法并没有改变总的比较次数，只是总的时间变小了，效率有所改进。

2.2冒泡排序若初始数据为正序，则一趟扫描就可以完成排序，关键字的比较次数为n-1，没有移动次数，即在最好的状况下，冒泡排序的时间繁杂度为O（n）；若初始数据为逆序，则比较次数和移动次数均达到最大值，最坏时间繁杂度为O（n2）。由汇总表可看出，该算法对于数据量大的排序的效率是很低的，使用改进的双向冒泡法进行排序时，效率有所改进，但仍为O（n2）。

2.3快速排序由汇总表中的正序和逆序数据可以看出，该算法对基本有序的初始记录进行排序的效率是很低的，其对初始序列的敏感程度大。快速排序的平均时间繁杂度约为1.39nlog2n，而且在所有排序方法当中的速度是最快的，特别是在处理大规模无序数据时，其优势更为明显。

2.4二路归并由汇总表可以看出，算法对初始序列的敏感程度