实验十二 排序算法

1、昆明理工大学信息工程与自动化学院学生实验报告（2013 2014 学年第三学期）课程名称：数据结构开课实验室：信自楼4422013年12月24日年级、专业、班计科122班 学号 201210405204 姓名邹华宇成绩实验项目名称简单的排序算法指导教师胡守成教师评语教师签名：年月日注：报告内容按实验须知中七点要求进行。一、实验目的和要求掌握各种查找算法理解和实现；增强上机编程调试能力；程序的主要功能用户输入任意个数，产生相应的随机数用户可以自己选择排序方式（直接插入排序、折半插入排序、起泡排序、快速排序、 选择排序、堆排序、基数排序）的一种程序给出原始数据、排序后从小到大的数据，并给出排序所用

2、的时间。二、实验原理及基本技术路线图（方框原理图）各个排序是算法思想：（1）直接插入排序：将一个记录插入到已排好的有序表中，从而得到一个新的, 记录数增加1的有序表。（2）折半插入排序：插入排序的基本插入是在一个有序表中进行查找和插入， 这个查找可利用折半查找来实现，即为折半插入排序。（3）起泡排序：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类 推，直到第N-1和第N个记录的关键字进行过比较为止。上述为第一趟排序，其结果 使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序， 对前N-1个记

3、录进行同样操作。一共要进行N-1趟起泡排序。（4）快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记 录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序， 已达到整个序列有序。（5）选择排序：通过N-I次关键字间的比较，从N-I+1个记录中选出关键字最 小的记录，并和第I（1=I=N）个记录交换。（6）堆排序：在堆排序的算法中先建一个大顶堆，既先选得一个关键字作为最 大的记录并与序列中最后一个记录交换，然后对序列中前N-1记录进行选择，重新将 它调整成一个大顶堆，如此反复直到排序结束。（7）基数排序：按最低位优先法先对低位关键字进行排序，直到对最高位关键 字

4、排序为止，经过若干次分配和收集来实现排序。三、所用仪器、材料（设备名称、型号、规格等）联想计算机一台Microsoft Visual c+ 6.0四、程序源代码（*cpp），业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业/*排序算法 设计要求：利用随机函数产生N个随机整数（N = 500，1000，1500，2000，2500，,30006,利用直接插入排序、折半插入排序，起泡排序、快速排序、|选择排序、堆排序，基数排序 七种排序方法 *业业业业业业业业业业业业业业业业业业，*/ #i

5、nclude stdio.h#include stdlib.h #include time.h计时#define ERROR 0#define OK 1#define OVERFLOW -2#define MAXSIZE 100000 用户自己规定排序的数字的长度typedef int Status;typedef structint*r; / r0闲置intlength; 顺序表的总长度Sqlist;构造一个空线性表Status InitSqlist(Sqlist &L)L.r=(int *)malloc(MAXSIZE*sizeof(int);分配存储空间if(!L.r)printf（存储

6、分配失败！）;exit(0); 存储分配失败L.length=0;/初始长度为 0 return OK;输入随机数并显示在界面上Status ScanfSqlist(int &N,Sqlist &L) int i;printf(请输入要排序的元素个数N:); scanf(%d,&N);for(i=1;i=N;i+)L.ri=rand(); 随机产生样本整数printf(nn);printf(随机产生了 %d个随机数，它们是：n,N);for(i=1;i=N;i+)printf(%7.2d ,L.ri); printf(nH);L.length=N; /存储线性表的长度 return OK;输出

7、排序之后的数据int i;printf(数据个数：);/输出数据个数printf(H%dn,L.length);printf(排序后的数据：(从左向右依次增大)n);/输出数据for(i=1;i=N;i+)printf(%7.2d ,L.ri);printf(nH);return OK;/fde ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale

8、de ale de ale de ale de ale de ale de ale de ale de ale de ale de *直接插入排序，业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业 *Status InsertSort(Sqlist &L)参考书 P265 算法 10.1int ij;if(L.length=0)printf(要排序的数据为空！)；return ERROR;if(L.riL.ri-1) /将 L.r插入有序子表L.r0=L.ri; 复制为监视哨Lri=Lri-1;fOr(j=i-2;L

9、.r0L.rj;j-)L.rj+1=L.rj; 记录后移Lrj+1=Lr0; 插入到正确位置return OK;/fde ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de /*/折半插入排序，业业业业业业业业业业业业

10、业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业 /*Status BInsertSort(Sqlist &L)参考书 P267 算法 10.2int ij,midjowhigh;if(L.length=0)printf(要排序的数据为空！);return ERROR;L.r0=L.ri; /将 L.ri暂存在 L.r0 low=1;high=i-1;while(low=high) /在rlow.high忡折半查找有序插入的位置 mid=(low+high)/2;if(L.r0=high+1;j-) 插入点后的数据后移 L.rj+1=L.r

11、j;L.rhigh+1=L.r0;将数据插入/for return OK; y业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业 /* *希尔排序ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale al

12、e ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale ale*/参考书P272算法10.4及10.5/*Status ShellInsert(Sqlist &L,int dk)/希尔插入排序dkint ij;/前后位置的增量是for(i=dk+1;i=L.length;i+)r0只是暂存单元，不是哨兵，if(L.ri0 & L.r0L.rj;j-=dk) L.rj+dk=L.rj;入

13、位置L.rj+dk=L.r0;记录后移,查找插/插入return OK;Status ShellSort(Sqlist &L,int dlta5,int t)/希尔排序int i;if(L.length=0)printf(要排序的数据为空！);return ERROR;for(i=0;it;i+)ShellInsert(L,dltai);return OK;*/一趟增量为dltak的插入排序，业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业/*/起泡排序业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业

14、业业业业业业业业业业业业业业业业业业业业业业业业业业业业业 /Status BubbleSort(Sqlist &L)int ij,t;if(L.length=0)printf(要排序的数据为空！)；return ERROR;for(j=1;jL.rj+1)/前面的数据后面数据时t=L.rj+1;L.rj+1=L.rj;L.rj=t; 将元素交换return OK;/fde ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de ale de

15、 ale de ale de ale de ale de ale de ale de ale de ale de ale de ale *快速排序，业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业*int Partition(Sqlist &L, int low, int high) /交换顺序表中子表 L.rlow.high 的记录，使得枢 轴记录到位，并返回其所在位置，此时在它之前(后)的记录均不大于它 int pivotkey; 记录关键字L.r0=L.rlow; 用子表的第一个纪录作枢轴纪录pivotkey=L.rlow; 用枢轴

16、纪录关键字 while (lowhigh)while(low=pivotkey)high-；L.rlow= L.rhigh; 将比枢轴记录小的记录移到低端while(lowhigh & L.rlow=pivotkey)low+;L.rhigh=L.rlow; 将比枢轴记录大的数移到高端L.rlow=L.r0; 枢轴记录到位return low;/Partition 函数void Qsort (Sqlist &L,int low, int high)int pivotloc;if (lowhigh) 长度大于1,可以进行pivotloc=Partition(L, low ,high);Qsort

17、(L,low,pivotloc-1);对低子表递归排序，pivotloc是枢轴位置Qsort(L,pivotloc+1,high); 对高子表递归排序/Qsort 函数Status QuickSort (Sqlist &L)printf(要排序的数据为空！);return ERROR;Qsort(L,1,Llength);return OK;/QuickSort，夕业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业*选择排序业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业 *Status ChooseSort

18、(Sqlist &L)int ij,k,t;if(L.length=0)printf(没有数据！);return ERROR;for(i=1;i=L.length;i+) /排序的趟数k=i;for(j=i+1;j=L.length;j+) 比较第i个元素以及其后的数据中最小的if(L.rjL.rk)k=j;if(i!=j) /将最小数据赋值给L.ri t=L.ri;L.ri=L.rk;L.rk=t;return OK;业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业/*堆排序，业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业/*

19、Status HeapAdjust(Sqlist &L,int s,int m) 调整 L.rs的关键字,使 L.rsm成大顶堆int i;Lr0=Lrs;for(i=2*s;i+1=m;i*=2) 沿数据较大的孩子结点向下筛选if(im & L.ri=L.ri) /L.r0插入在 S 位置上 break;Lrs=Lri;s=i;L.rs=L.r0; /插入新数据return OK;Status HeapSort(Sqlist &L) 堆排序int i,t;if(L.length=0)printf(没有数据！)；return ERROR;for(i=L.length/2;i0;i-)HeapA

20、djust(L,i,Llength);for(i=L.length;i1;i-)t=L.r1; 将堆顶记录和当前未经排序的子序列L.r1.i中最后一个记录互换L.r1=L.ri;L.ri=t;HeapAdjust(L,1,i-1); 将 L.r1.i-1 重新调整为大顶堆return OK;业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业*基数排序业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业 亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍

21、亍亍typedef struct node( int key;node *next;RecType;Status RadixSort(Sqlist L)int t4j,k,d,n=1,m;RecType *p,*s,*q,*head10,*tail10; 定义各链队的首尾指针for(i=1;ikey=L.ri;if(i=1) 当为第一个元素时q=s;p=s;t+;elseq-next=s; 将链表连接起来q=s;t+;q-next=NULL;d=1;while(n0)将每个元素分配至各个链队for(j=0;jkey/d;k=k%10;if(headk=NULL) 进行分配headk=p;tai

22、lk=p;elsetailk-next=p;tailk=p;p=p-next; /取下一个待排序的元素p=NULL; /用于收集第一个元素时的判断 for(j=0;jnext=headj;q=tailj;q-next=NULL; 最后一个结点的next置为空d=d*10;n=0;m=1;while(mkey;i+;p=p-next;return OK;业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业 亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍主函数，业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业业*voi

23、d main()Sqlist L;Sqlist L0;InitSqlist(L); /初始化 LInitSqlist(L0);int m,i;char choice=z;clock_t start, finish; /定 义 clock_t 用于计时 double duration;霎 Yshkfe侦 =)supd f(=5 墓 Y着二 =)supdx=f.mupdmMrdf(a=)Jwdf(m=)updfr目 =)upd ?)Jwd,6=fcmft常职壑Tr=)upd 震置=)supd r5 重 Yghkfe侦 =)扫upd f(mftYKffiw二 二)JWJdf(=?)Jwd sTa昌b

24、sjiwos fr3帐埼田殿 8 f(m重警 K =)upd fr目重,9 =)supd f(mtt:董般In=)扫upd fr定常瑕塾 4tzJWIdprintf(5、选择排 序n);printf(6、堆排 序n);printf(7、基数排 序n);printf(8、退出该系统nn);printf(n请选择排序的方式,数字1-7:);scanf(%d,&choice); 选择排序方式赋值choice，用于后面的函数选择while(choice8)printf(输入方式有误。n请输入1-7选择排序方式，或者选择8退出系统);scanf(%d,&choice);while(choice!=8)f

25、or(i=1;i=L0.length;i+)L.ri=L0.ri;L.length=L0.length;switch(choice)case 1:/直接插入排序start = clock();InsertSort(L);finish = clock();break;case 2:/折半插入排序start = clock();BlnsertSort(L); finish = clock(); break;case 3:/起泡排序start = clock(); BubbleSort(L); finish = clock(); break;case 4:快速排序start = clock(); Q

26、uickSort(L); finish = clock(); break;case 5:选择排序start = clock(); ChooseSort(L); finish = clock(); break;case 6:/堆排序start = clock(); HeapSort(L); finish = clock(); break;case 7:/基数排序start = clock(); RadixSort(L); finish = clock(); break;case 8:/直接退出break;PrintfSqlist（m,L）; /输出数据和L的长度duration = （doubl

27、e）（finish - start） / CLOCKS_PER_SEC;/输出算术时间printf（n本次排序运算所用的时间是：%lf secondsn,duration）;printf（本次排序结束。n）;printf（n）;printf（继续本系统吗？ nn）;printf（以下是各个排序算法的代号：n）;printf（1、直接插入排序n）;printf（2、折半插入排序n）;printf（3、起泡排序皿”）；printf（4、快速排序寸）；printf（5、选择排序皿”）；printf（6、堆排序皿”）；printf（7、基数排序寸）；printf（ 8、退出该系统皿”）；printf（

28、n请请输入1-7选择排序方式，或者选择8退出系统:）；scanf（%d,&choice）;while（choice8）printf（输入方式有误。n请输入1-7选择排序方式，或者选择8退出系统）;scanf（%d,&choice）;五、运行结果1、首先选择需要排序的数字个数，比如输入5000。算法排序比较系统序序lF.LF,. 亡冗 速择囊出 直霜快选堆基退 侦2.3.4.5.6.L8.请输入要排序的元素个数N: 5000,2、系统显示出随机产生的随机数。用户选择排序方式，比如选择1直接插入排序i-7：cr.lrlr.直霰快选堆基退1.2.3.4.5.6.7.8.-f.lf.n，芒A-X序序序 -13.-13._ - _ - _. - - _.-9107 31098 4583 13877 7285 27626 4493 2