数据结构各种排序算法的课程设计实验报告(c语言版).doc

滁州学院课程设计报告课程名称： 数据结构 设计题目： 排序算法实现及比较 系 别： 计算机信息工程学院 专 业： 计算机科学与技术 组 别： 第*组 起止日期: 12 年 5 月 1 日 12 年 6月 1 日 指导教师: * 计算机与信息工程学院二一二年制课程设计任务书课程设计题目排序算法实现将比较组长*学号20*班级*系别计算机与信息工程学院专业计算机科学与技术组员*指导教师*课程设计目的加深对常见排序算法理解通过程序比较常见算法优越性熟悉加深对数据结构的了解及认识课程设计所需环境Windows xp；VC+6.0课程设计任务要求实现常见排序算法程序化测试程序比较算法优越性了解常见算法的实际应用课程设计工作进度计划序号起止日期工 作 内 容分工情况1分析实验类容2分工3算法改编成程序4将子程序合并及调试数据测试及记录5编写报告指导教师签字： 年 月 日系（教研室）审核意见：系（教研室）主任签字： 年 月 日目 录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.需求分析 本课程题目是排序算法的实现，由于各方面的原因，本课程设计一共要设计七种排序算法。这七种算法共包括：直接插入排序，折半插入排序，希尔排序，简单选择排序，堆排序，归并排序，冒泡排序。七种排序各有独到之处，因此我们要通过各种调试分析来比较其优劣长短。 为了小组分工的方便，我们特意把子函数写成Header File文件。这样操作不仅可以使小组分工更加简洁明了，还可以方便子函数的调用，更可以使写主函数时一目了然。 为了运行时的方便，我们将七种排序方法进行编号，其中1为直接插入排序，2为折半插入排序，3为希尔排序，4为简单选择排序，5为堆排序，6为归并排序，7为冒泡排序。通过这七种选项，可以让用户简单明了的去选择使用哪一种排序方法。 本课程就是通过对5组占用内存大小不同的数据调试来测试这七种算法运行的时间长短，从中选择面对不同大小的文件时，哪一种算法更为快捷。 软件环境本课程设计所用操作系统为Windows-XP操作系统，所使用的软件为Microsoft Visual C+ 6.0；3.详细设计3.1 直接插入排序算法思想：直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到一个已排好序的有序表中，从而得到一个新的、记录数增一的有序表。在自i-1起往前搜索的过程中，可以同时后移记录。整个排序过程为进行n-1趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。程序实现及核心代码的注释：for (i = 1 ; i < r.length ;+i )for(j=0;j < i;+j)if(r.basei < r.basej)temp = r.basei; /保存待插入记录for(i= i ;i > j; -i )r.basei = r.basei-1; /记录后移r.basej = temp; /插入到正确的为位置r.baser.length ='0'3.2折半排序算法思想：由于折半插入排序的基本操作是在一个有序表中进行查找和插入，这个“查找”操作可利用折半查找来实现，由此进行的插入排序称之为折半插入排序。折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，这般插入排序仅减少了关键字间的比较次数，而记录的移动次数 不变。因此，这般插入排序的时间复杂度仍为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 < r.basem )high = m-1; /插入低半区elselow = m+1; /插入高半区for( j=i-1; j>=high+1; -j ) r.basej+1= r.basej; /记录后移 r.basehigh+1=temp; /插入3.3 希尔排序算法思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。其中，子序列的构成不是简单的“逐段分割”，而是将分隔某个“增量”的记录组成一个子序列。程序实现及核心代码的注释：for(k = 0; k < 10 ; k+)m = 10 - k;for( i = m ; i < r.length; i + )if(r.basei < r.basei - m) temp = r.basei; /保存待插记录 for(j = i - m ; j >= 0 && temp < r.basej; j -= m)r.base j + m = r.basej; /记录后移，查找插入位置 r.base j + m = temp; /插入3.4简单选择排序算法思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。程序实现及核心代码的注释：for ( i = 0 ; i < r.length ; i+ ) /i为排好序的数的下标，依次往后存放排 /好序的数 temp=r.basei; /将待放入排好序的数的下标的数保存 for( j = i,m = j +1 ; m < r.length ; m+) /找出未排序的数中最小的数的循环；if(r.basej > r.basem) j = m; r.basei = r.basej; /把下标为j的数与i数互换；r.basej = temp; 3.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); 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( (j<m) && (rj>rj+1) )j+;if(x>rj) /插入字符比当前的大，交换ri =rj;i = j;j *= 2;else /否则比较停止。j = m + 1;ri = x; /把字符x插入到该位置，元素插入实现3.6归并排序 算法思想：先将相邻的个数为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+; if(r.basei <= r.basej) /将第一组数据与第二组数据分别比较；t.basek = r.basei+;elset.basek = r.basej+; if(i > 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) /考虑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(s<n) /每组元素不断增加循环进行合并排序； tgb(s,n,r,t); / s为每组元素的个数、n为元素总个数、r /为原数组，t为待排序的数组，进行归并排s*=2; /序；把元素个数相同的两组合并 并进行重新 /定义成新的一组，此组元素个数为2*s；if(s<n) tgb(s,n,t,r); s *= 2; /当元素个数小于n时，对其进行合并排序；else /当元素个数大于n时，对剩下的数排序； i=0;while(i<=n) r.basei=t.basei+1;i+; 3.7冒泡排序算法思想：1、先将一组未排序的数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，然后将比较后的较小的数与倒数第三个进行比较，依次比较到第一个数，即可得到第一个数是所有数中最小的数；2、然后再将数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，依次比较到第二个数，3、如此循环到只剩最后两个比较，即得到排好序的一组数。程序实现及核心代码的注释：for( i=0; i < r.length ;i+ ) / i为排好序的数的下标，依次往后存放排好序的数； for( j = r.length-2;j >= i;j - ) /从后往前依次两两比较，较小的被调换到前面 ； if(r.basej+1 < r.basej) /比较相邻两个数，如果后面的小于前面的，向下执行； temp = r.basej+1; /将后面的较小的数保存起来；r.basej+1 = r.basej; /将前面的较大的数放在后面较小的数的位置；r.basej = temp; /将较小的数放在前面的较大的数的位置； 4.调试检测主函数是否能够稳定运行(如图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简单选择排序输入字符并保存（如图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图5-7.36.测试与比较6.1调试步骤 在kcsj文本文件中随机输入一串字符串，然后保存下来并且复制备份在桌面上。运行程序，调用不算法去处理文件。用秒表计算从开始到结束所用的时间，并记录下来。 将文件夹中的kcsj文本文件删除，将桌面上的备份文件考入文件夹来代替原文件，以保障被操作数据的一致性。 用同样的方法依次测试七种算法所用的时间，并记录下来。 再将数据依次改变为占用内存大小为50KB 、100KB、200KB、512KB、1024KB的数字串，重复以上的操作。 将记录的数据（如表6-1）。表6-1 同一文件不同算法处理的时间表直接插入排序折半插入排序希尔排序简单选择排序堆排序归并排序冒泡排序50KB>1m1.5s0.2s6.0s<0.1s<0.1s6.1s100KB>3m5.5s1.1s23s<0.1s<0.1s24s200KB-20s3.8s-<0.1s<0.1s>1m512KB->1m14s-<0.1s0.1s>3m1024KB->3m>1m-0.2s0.3s>10m-：表示时间过长6.2结论 通过实验结果的比较与分析我们发现：直接插入排序、冒泡排序、简单选择排序及折半插入排序是低效率的排序方式；所以我们实际编程重要尽可能的避免他们的出现；我们应该用较先进的归并排序及堆排序。7.实验心得与分析 通过本次课程设计，我们小组的每个成员都学到了很多东西。首先要说的是我们的编程能力，在这一次的课程设计中我们的编程能力均得到了一定程度的提升。并且通过这次课程设计，我们更加熟悉了如何使用Header File文件。本次课程设计，让我们对于直接插入排序，折半插入排序，希尔排序，简单选择排序，堆排序，归并排序，冒泡排序等七种排序算法的思想有了进一步的认识，同时对七种算法的应用有了更进一步的掌握。通过这次课程设计，我们对于解决实际问题的能力有了进一步提高。最重要的是，这次课程设计大大的训练了我们的小组团队协作能力。通过这次课程设计我们小组各成员的团队协作能力都有了很大的提升。这种团队协作能力对于我们学编程的来说是极其重要的，同时也是必不可少的。 当然，我们写程序的时候遇到了很多困难。而且在程序调试过程中出现了很多错误与警告，不过在队员及老师的帮助下均得到了解决。当程序可以运行后，程序的运行过程中同样也也出现了很多错误，甚至出现了不兼容的情况。不过，后来在队员及老师的帮助下也均得到了解决。然而，我们的程序还有一点瑕疵让我们感到美中不足。那就是在归并算法运行过程中，当输入为9个字符时，排序结果会出现偶然误差。经过分析，我们认为这点是系统的问题。不过，这仍然是一点让我们感到遗憾的地方。8.附录8.1直接插入排序#include<stdio.h>#include<stdlib.h>#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)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 - r.length;for (i = 1 ; i < r.length ;+i )for(j=0;j < i;+j)if(r.basei < r.basej)temp = r.basei;for(i= i ;i > 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<stdio.h>#include<stdlib.h>#define Q 1000typedef struct char *base ; int stacksize ;int length;SqList2; void zb(FILE *fp) SqList2 r;int i,j ,m, low, 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.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 < r.basem )high = m-1; elselow = m+1; for( j=i-1; j>=high+1; -j )r.basej+1= r.basej; r.basehigh+1=temp; r.baser.length ='0'rewind(fp);fprintf(fp,"%s",r.base);fclose(fp);free(r.base);8.3希尔排序#include<stdio.h>#include<stdlib.h>#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.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(k = 0; k < 10 ; k+)m = 10 - k;for( i = m ; i < r.length; i + )if(r.basei < r.basei - m) temp = r.basei; for(j = i - m ; j >= 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<stdio.h>#include<stdlib.h>#define Q 1000typedef struct char *base ; int stacksize ;int length;SqList4; void jd(FILE *fp) SqList4 r;int i,j ,m;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.base = r.base + 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.length ; m+)if(r.basej > r.basem)j = m;r.basei = r.basej;r.basej = temp;r.baser.length ='0'rewind(fp);fprintf(fp,"%s",r.base); fclose(fp);