数据结构各种排序实验报告

《数据结构各种排序实验报告》由会员分享，可在线阅读，更多相关《数据结构各种排序实验报告（32页珍藏版）》请在装配图网上搜索。

1、目 录1.引言42.需求分析43.详细设计43.1 直接插入排序43.2折半排序53.3 希尔排序63.4简单选择排序63.5堆排序63.6归并排序73.7冒泡排序94.调试105.调试及检验115.1 直接插入排序115.2折半插入排序115.3 希尔排序125.4简单选择排序125.5堆排序135.6归并排序145.7冒泡排序146.测试与比较156.1调试步骤156.2结论167.实验心得与分析168.附录178.1直接插入排序178.2折半插入排序188.3希尔排序208.4简单选择排序228.5堆排序238.6归并排序268.7冒泡排序298.8主程序301.需求分析 课程题目是排序

2、算法的实现，课程设计一共要设计八种排序算法。这八种算法共包括：堆排序，归并排序，希尔排序，冒泡排序， 快速排序，基数排序，折半插入排序，直接插入排序。 为了运行时的方便，将八种排序方法进行编号，其中1为堆排序，2为归并排序，3为希尔排序，4为冒泡排序，5为快速排序，6为基数排序，7为折半插入排序8为直接插入排序。 软件环境： Windows-7操作系统，所使用的软件为c-Free；2.概要设计 2.1 直接插入排序算法思想：直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到一个已排好序的有序表中，从而得到一个新的、记录数增一的有序表。在自i-1起往前搜索的过程中，可以同时后移记

3、录。整个排序过程为进行n-1趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。程序实现及核心代码的注释：for (i = 1 ; i r.length ;+i )for(j=0;j i;+j)if(r.basei j; -i )r.basei = r.basei-1; /记录后移r.basej = temp; /插入到正确的为位置r.baser.length =0;2.2折半排序算法思想：由于折半插入排序的基本操作是在一个有序表中进行查找和插入，这个“查找”操作可利用折半查找来实现，由此进行的插入排序称之为折半

4、插入排序。折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，这般插入排序仅减少了关键字间的比较次数，而记录的移动次数 不变。因此，这般插入排序的时间复杂度仍为O（n2）。程序实现及核心代码的注释：void zb(FILE *fp) /对顺序表作折半插入排序for ( i = 1 ; i r.length ; i+ )temp=r.basei; /将r.basei寄存在temp中low=0;high=i-1; while( low = high ) /在baselow到keyhigh中折 半查找有序插入的位置 m = (low+high)/2; /折半if ( temp =high+

5、1; -j ) r.basej+1= r.basej; /记录后移 r.basehigh+1=temp; /插入2.3 希尔排序算法思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。其中，子序列的构成不是简单的“逐段分割”，而是将分隔某个“增量”的记录组成一个子序列。程序实现及核心代码的注释：for(k = 0; k 10 ; k+)m = 10 - k;for( i = m ; i r.length; i + )if(r.basei = 0 & temp r.basej; j -= m)r.base j +

6、m = r.basej; /记录后移，查找插入位置 r.base j + m = temp; /插入2.4简单选择排序算法思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。程序实现及核心代码的注释：for ( i = 0 ; i r.length ; i+ ) /i为排好序的数的下标，依次往后存放排 /好序的数 temp=r.basei; /将待放入排好序的数的下标的数保存 for( j = i,m = j +1 ; m r.basem) j = m; r.basei = r.basej

7、; /把下标为j的数与i数互换；r.basej = temp; 2.5堆排序算法思想：堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。将序列所存储的元素AN看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。算法的平均时间复杂度为O(N log N)。程序实现及核心代码的注释：void dp(FILE *fp)for(i = r.length / 2;i = 1 ; -i) /把r.base1.r.length建成大顶堆HeapAdjust(r.base,i,r.length);

8、 for(i = r.length ;i = 2 ; -i) temp = r.base1; r.base1 = r.basei; r.basei = temp;HeapAdjust(r.base,1,i-1); /将r.base1.i-1重新调整为大顶堆void HeapAdjust(char *r,int k,int m) i=k; x=ri; j=2*i; /沿key 较大的孩子节点向下筛选while(j=m) /j为key较大的记录的下标 if( (jrj+1) )j+;if(xrj) /插入字符比当前的大，交换ri =rj;i = j;j *= 2;else /否则比较停止。j =

9、m + 1;ri = x; /把字符x插入到该位置，元素插入实现2.6归并排序1 算法思想：先将相邻的个数为1的每两组数据进行排序合并；然后对上次归并所得到的大小为2的组进行相邻归并；如此反复，直到最后并成一组，即排好序的一组数据。程序实现及核心代码的注释：void merge(SqList6 r,int h ,int m ,int w ,SqList6 t) /对相邻两组数据进行组合排序；int i,j,k;i = h ; j = m + 1; /j为合并的第二组元素的第一个数位置 k =h-1； / k为存入t中的数的位置；while(i = m)&(j = w) /依次排列两组数据k+;

10、 if(r.basei m) /第一组数据先排完的情况while(j = w) t.base+k=r.basej+;else while(i = m) t.base+k=r.basei+;void tgb(int s,int n,SqList6 r,SqList6 t) /对数据进行每组s个数的归并排序；int i=1; /i为要合并两组元素的第一个数位置；while(i=(n-2*s+1) merge(r,i,i+s-1,i+2*s-1,t); /i+s-1为要合并的第一组元素的最后一/数位置、i+2*s-1 为要合并的两组元素/最后一个数位置；i=i+2*s;if(i(n-s+1) /考虑

11、n不能被s整除，如果余下的数少于/2*s 但大于s，也就是余下的数不能凑成/两组，凑一组有余,则把余下的数进行组/合，并对其进行排序； merge(r,i,i+s-1,n,t);else /如果余下的数少于s，则余下的数进行组/合，并进行排序；while(i=n) t.basei=r.basei+;void gb(FILE *fp) / 归并主函数； n = r.length; SqList6 t;t.base=(char *) malloc(r.stacksize*sizeof(char); /给待排序的数组t申请内存； while(sn) /每组元素不断增加循环进行合并排序； tgb(s,

12、n,r,t); / s为每组元素的个数、n为元素总个数、r /为原数组，t为待排序的数组，进行归并排s*=2; /序；把元素个数相同的两组合并 并进行重新 /定义成新的一组，此组元素个数为2*s；if(sn) tgb(s,n,t,r); s *= 2; /当元素个数小于n时，对其进行合并排序；else /当元素个数大于n时，对剩下的数排序； i=0;while(i=n) r.basei=t.basei+1;i+; 2.7冒泡排序算法思想：1、先将一组未排序的数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，然后将比较后的较小的数与倒数第三个进行比较，依次比较到第一个数

13、，即可得到第一个数是所有数中最小的数；2、然后再将数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，依次比较到第二个数，3、如此循环到只剩最后两个比较，即得到排好序的一组数。程序实现及核心代码的注释：for( i=0; i = i;j - ) /从后往前依次两两比较，较小的被调换到前面 ； if(r.basej+1 r.basej) /比较相邻两个数，如果后面的小于前面的，向下执行； temp = r.basej+1; /将后面的较小的数保存起来；r.basej+1 = r.basej; /将前面的较大的数放在后面较小的数的位置；r.basej = temp; /将较

14、小的数放在前面的较大的数的位置； 3.调试检测主函数是否能够稳定运行(如图4-1)：图4-15.调试及检验5.1 直接插入排序输入字符并保存（如图5-1.1）：调用算法【1】处理文件（如图5-1.2）：处理结果（如图5-1.3）：图5-1.1 图5-1.2图5-1.35.2折半插入排序输入字符并保存（如图5-2.1）：调用算法【2】处理文件（如图5-2.2）：处理结果（如图5-2.3）：图5-2.1 图5-2.2图5-2.35.3 希尔排序输入字符并保存（如图5-3.1）：调用算法【3】处理文件（如图5-3.2）：处理结果（如图5-3.3）：图5-3.1 图5-3.2图5-3.35.4简单选择

15、排序输入字符并保存（如图5-4.1）：调用算法【4】处理文件（如图5-4.2）：处理结果（如图5-4.3）：图5-4.1 图5-4.2图5-4.35.5堆排序输入字符并保存（如图5-5.1）：调用算法【5】处理文件（如图5-5.2）：处理结果（如图5-5.3）：图5-5.1 图5-5.2图5-5.35.6归并排序输入字符并保存（如图5-6.1）：调用算法【6】处理文件（如图5-6.2）：处理结果（如图5-6.3）：图5-6.1 图5-6.2图5-6.35.7冒泡排序输入字符并保存（如图5-7.1）：调用算法【7】处理文件（如图5-7.2）：处理结果（如图5-7.3）：图5-7.1 图5-7.2

16、图5-7.36.2结论 通过实验结果的比较与分析我们发现：直接插入排序、冒泡排序、简单选择排序及折半插入排序是低效率的排序方式；所以我们实际编程重要尽可能的避免他们的出现；我们应该用较先进的归并排序及堆排序。7.实验心得与分析 通过本次课程设计，我们小组的每个成员都学到了很多东西。首先要说的是我们的编程能力，在这一次的课程设计中我们的编程能力均得到了一定程度的提升。并且通过这次课程设计，我们更加熟悉了如何使用Header File文件。本次课程设计，让我们对于直接插入排序，折半插入排序，希尔排序，简单选择排序，堆排序，归并排序，冒泡排序等七种排序算法的思想有了进一步的认识，同时对七种算法的应用

17、有了更进一步的掌握。通过这次课程设计，我们对于解决实际问题的能力有了进一步提高。最重要的是，这次课程设计大大的训练了我们的小组团队协作能力。通过这次课程设计我们小组各成员的团队协作能力都有了很大的提升。这种团队协作能力对于我们学编程的来说是极其重要的，同时也是必不可少的。 当然，我们写程序的时候遇到了很多困难。而且在程序调试过程中出现了很多错误与警告，不过在队员及老师的帮助下均得到了解决。当程序可以运行后，程序的运行过程中同样也也出现了很多错误，甚至出现了不兼容的情况。不过，后来在队员及老师的帮助下也均得到了解决。然而，我们的程序还有一点瑕疵让我们感到美中不足。那就是在归并算法运行过程中，当输

18、入为9个字符时，排序结果会出现偶然误差。经过分析，我们认为这点是系统的问题。不过，这仍然是一点让我们感到遗憾的地方。8.附录8.1直接插入排序#include#include#define Q 1000typedef struct char *base ; int stacksize ; int length;SqList1; void zj(FILE *fp) SqList1 r;int i,j;char temp,*p; r.base=(char *) malloc(Q*sizeof(char);r.stacksize = Q;r.length = 0; while(!feof(fp)fs

19、canf(fp,%c,r.base); r.base+;r.length+;if(r.length = r.stacksize )r.base= r.base - r.length;r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char);if(!r.base)printf(ERROR);return ; r.base = r.base + r.stacksize;r.stacksize += Q; r.length -;r.base -;r.base= r.base - r.length;for (i = 1 ; i r.

20、length ;+i )for(j=0;j i;+j)if(r.basei j; -i )r.basei = r.basei-1;r.basej = temp;r.baser.length =0;rewind(fp);fprintf(fp,%s,r.base); fclose(fp);free(r.base);8.2折半插入排序#include#include#define Q 1000typedef struct char *base ; int stacksize ;int length;SqList2; void zb(FILE *fp) SqList2 r;int i,j ,m, lo

21、w, high;char temp; r.base=(char *) malloc(1000*sizeof(char);r.stacksize = 1000;r.length = 0; while(!feof(fp)fscanf(fp,%c,r.base);r.base+;r.length+;if(r.length = r.stacksize )r.base= r.base - r.length;r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char);if(!r.base)printf(ERROR);return ; r.

22、base = r.base + r.stacksize;r.stacksize += Q; r.length -;r.base -;r.base= r.base - r.length;for ( i = 1 ; i r.length ; i+ )temp=r.basei; low=0;high=i-1;while( low = high ) m = (low+high)/2; if ( temp =high+1; -j )r.basej+1= r.basej; r.basehigh+1=temp; r.baser.length =0;rewind(fp);fprintf(fp,%s,r.bas

23、e);fclose(fp);free(r.base);8.3希尔排序#include#include#define Q 1000typedef struct char *base ; int stacksize ;int length;SqList3; void xe(FILE *fp) SqList3 r;int i,j,k,m;char temp;r.length = 0; r.base=(char *) malloc(1000*sizeof(char);r.stacksize = 1000; while(!feof(fp)fscanf(fp,%c,r.base);r.base+;r.le

24、ngth+;if(r.length = r.stacksize )r.base= r.base - r.length;r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char);if(!r.base)printf(ERROR);return ; r.base = r.base + r.stacksize;r.stacksize += Q; r.length -;r.base -;r.base= r.base - r.length;for(k = 0; k 10 ; k+)m = 10 - k;for( i = m ; i r.

25、length; i + )if(r.basei = 0 & temp r.basej; j -= m)r.base j + m = r.basej; r.base j + m = temp; rewind(fp);fprintf(fp,%s,r.base);fclose(fp);free(r.base);8.4直接选择排序#include#include#define Q 1000typedef struct char *base ; int stacksize ;int length;SqList4; void jd(FILE *fp) SqList4 r;int i,j ,m;char t

26、emp; r.base=(char *) malloc(1000*sizeof(char);r.stacksize = 1000;r.length = 0; while(!feof(fp)fscanf(fp,%c,r.base);r.base+;r.length+;if(r.length = r.stacksize )r.base= r.base - r.length;r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char);if(!r.base)printf(ERROR);return ; r.base = r.base

27、+ r.stacksize;r.stacksize += Q; r.length -;r.base -;r.base= r.base - r.length;for ( i = 0 ; i r.length ; i+ )temp=r.basei; for( j = i,m = j +1 ; m r.basem)j = m;r.basei = r.basej;r.basej = temp;r.baser.length =0;rewind(fp);fprintf(fp,%s,r.base); fclose(fp);free(r.base);8.5堆排序#include#include#define

28、Q 1000typedef struct char *base ; int stacksize ; int length;SqList5; void HeapAdjust(char *r,int s,int m);void dp(FILE *fp) SqList5 r;int i,j;char temp,*k;r.length = 0; r.base=(char *) malloc(1000*sizeof(char);r.stacksize = 1000;r.base += 1; while(!feof(fp)fscanf(fp,%c,r.base);r.base+;r.length+;if(

29、r.length = (r.stacksize - 1) )r.base= r.base - r.length - 1;r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char);if(!r.base)printf(ERROR);return ; r.base = r.base + r.stacksize;r.stacksize += Q; r.length -;r.base -;r.base= r.base - r.length - 1;for(i = r.length / 2;i = 1 ; -i)HeapAdjust(r

30、.base,i,r.length); for(i = r.length ;i = 2 ; -i)temp = r.base1; r.base1 = r.basei;r.basei = temp;HeapAdjust(r.base,1,i-1);k = (char *) malloc(r.length+1)*sizeof(char); for(i = r.length,j = 0; i = 1; i-,j+)kj = r.basei;kj=0;rewind(fp); fprintf(fp,%s,k); fclose(fp);free(k);free(r.base);void HeapAdjust

31、(char *r,int k,int m)int i,j;char x;i=k; x=ri; j=2*i;while(j=m) if( (jrj+1) )j+;if(xrj) ri =rj;i = j;j *= 2;else j = m + 1;ri = x;8.6归并排序#include#include#define Q 1000typedef struct char *base ; int stacksize ; int length;SqList6; void merge(SqList6 r,int h,int m,int w,SqList6 t) int i,j,k;i = h; j

32、= m + 1; k = h - 1;while(i = m)&(j = w) k+;if(r.basei m)while(j = w) t.base+k=r.basej+;elsewhile(i = m) t.base+k=r.basei+;void tgb(int s,int n,SqList6 r,SqList6 t) int i=1;while(i=(n-2*s+1) merge(r,i,i+s-1,i+2*s-1,t);i=i+2*s;if(i(n-s+1) merge(r,i,i+s-1,n,t);else while(i=n) t.basei=r.basei+;void gb(F

33、ILE *fp) SqList6 r;r.length = 0; r.base=(char *) malloc(1000*sizeof(char);r.stacksize = 1000;r.base += 1;while(!feof(fp)fscanf(fp,%c,r.base);r.base+;r.length+;if(r.length = (r.stacksize - 1) )r.base= r.base - r.length - 1;r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char);if(!r.base)pri

34、ntf(ERROR);return ; r.base = r.base + r.stacksize;r.stacksize += Q; r.length -;r.base= r.base - r.length - 2; int i,j,n,s=1;n = r.length; SqList6 t; t.base=(char *) malloc(r.stacksize*sizeof(char); while(sn) tgb(s,n,r,t);s*=2;if(sn) tgb(s,n,t,r); s *= 2; else i=0;while(i=n) r.basei=t.basei+1;i+; r.b

35、aser.length =0;rewind(fp); fprintf(fp,%s,r.base); fclose(fp);free(t.base);free(r.base);8.7冒泡排序#include#include#define Q 1000typedef struct char *base ; int stacksize ;int length;SqList7; void mp(FILE *fp) SqList7 r;int i,j ,m;char temp;r.length = 0; r.base = (char *) malloc(1000*sizeof(char);r.stack

36、size = 1000;while(!feof(fp)fscanf(fp,%c,r.base);r.base+;r.length+;if(r.length = r.stacksize )r.base= r.base - r.length;r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char);if(!r.base)printf(ERROR);return ; r.base = r.base + r.stacksize;r.stacksize += Q; r.length -;r.base -;r.base= r.base

37、- r.length;for( i=0; i = i;j - ) if(r.basej+1 r.basej)temp = r.basej+1; r.basej+1 = r.basej;r.basej = temp;m = 0;if( m ) break; r.baser.length =0;rewind(fp);fprintf(fp,%s,r.base);fclose(fp);free(r.base);8.8主程序#include#includezj.h#includezb.h#includexe.h#includejd.h#includemp.h#includedp.h#includegb.

38、hvoid main()FILE *fp;int sign;while(sign != 0)printf(请选择：n);printf( %6c 1直接插入排序n, );printf( %6c 2折半插入排序n, );printf( %6c 3希尔排序n, );printf( %6c 4简单选择排序n, );printf( %6c 5堆排序n, );printf( %6c 6归并排序n, );printf( %6c 7冒泡排序n, );printf( %6c 0退出n, );printf(请输入：);scanf(%d,&sign);if(fp=fopen(kcsj.txt,r+)=NULL)printf( File open error!n);return;switch(sign)case 1: zj(fp);break;case 2:zb(fp);break;case 3:xe(fp);break;case 4:jd(fp);break;case 5: dp(fp);break;case 6: gb(fp);break;case 7: mp(fp);break;case 0:break;printf(n n n);评语： 评阅教师签名： 年 月 日成 绩