2022年数据结构各种排序算法的课程设计实验报告 2.pdf

《2022年数据结构各种排序算法的课程设计实验报告 2.pdf》由会员分享，可在线阅读，更多相关《2022年数据结构各种排序算法的课程设计实验报告 2.pdf（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、课 程 设 计 报 告课程名称：数据结构设计题目：排序算法实现及比较系别：计算机信息工程学院专业：计算机科学与技术组别：第*组起止日期:12 年 5 月 1 日 12 年 6 月 1 日指导教师:*计算机与信息工程学院二 一二年制名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 33 页 -课程设计任务书课程设计题目排序算法实现将比较组长*学号20*班级*系别计算机与信息工程学院专业计算机科学与技术组员*指导教师*课程设计目的加深对常见排序算法理解通过程序比较常见算法优越性熟悉加深对数据结构的了解及认识课程设计所需环境Windows xp；VC+6.0 课程设计任务要求实现常见排序

2、算法程序化测试程序比较算法优越性了解常见算法的实际应用课程设计工作进度计划序号起止日期工作内容分工情况1 分析实验类容2 分工3 算法改编成程序4 将子程序合并及调试数据测试及记录5 编写报告指导教师签字：年月日系（教研室）审核意见：系（教研室）主任签字：年月日名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 33 页 -目 录1.引言.4 2.需求分析.4 3.详细设计.4 3.1 直接插入排序.4 3.2 折半排序.5 3.3 希尔排序.6 3.4 简单选择排序.6 3.5 堆排序.6 3.6 归并排序.7 3.7 冒泡排序.9 4.调试.10 5.调试及检验.11 5.1 直

3、接插入排序.11 5.2 折半插入排序.11 5.3 希尔排序.12 5.4 简单选择排序.12 5.5 堆排序.13 5.6 归并排序.14 5.7 冒泡排序.14 6.测试与比较.15 6.1 调试步骤.15 6.2 结论.16 7.实验心得与分析.16 8.附录.17 8.1 直接插入排序.17 8.2 折半插入排序.18 8.3 希尔排序.20 8.4 简单选择排序.22 8.5 堆排序.23 8.6 归并排序.26 8.7 冒泡排序.29 8.8 主程序.30 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 33 页 -1.引言伴随着社会的发展，数据也变得越来越庞大。如

4、何将庞大的数据进行很好的排序，使用户更加方便的查找资料，成了一件越来越重要的问题。对于程序员来说，这将是一个挑战。经常查找资料的朋友都会知道，面对海量的资料，如果其查找的资料没有进行排序，那么其查找资料将会是一件非常痛苦的事情。针对这一问题，我们自此通过一个课程设计来解决它。理论上排序算法有很多种，不过本课程设计只涉及到七种算法。这七种算法共包括：直接插入排序，折半插入排序，希尔排序，简单选择排序，堆排序，归并排序，冒泡排序。本课程设计通过对这七种算法的运行情况进行对比，选择最优秀的算法来提供给用户。希望通过我们的努力能给用户解决一些问题，带来一些方便。2.需求分析本课程题目是排序算法的实现，

5、由于各方面的原因，本课程设计一共要设计七种排序算法。这七种算法共包括：直接插入排序，折半插入排序，希尔排序，简单选择排序，堆排序，归并排序，冒泡排序。七种排序各有独到之处，因此我们要通过各种调试分析来比较其优劣长短。为了小组分工的方便，我们特意把子函数写成Header File 文件。这样操作不仅可以使小组分工更加简洁明了，还可以方便子函数的调用，更可以使写主函数时一目了然。为了运行时的方便，我们将七种排序方法进行编号，其中1 为直接插入排序，2 为折半插入排序，3 为希尔排序，4 为简单选择排序，5 为堆排序，6 为归并排序，7 为冒泡排序。通过这七种选项，可以让用户简单明了的去选择使用哪一

6、种排序方法。本课程就是通过对5 组占用内存大小不同的数据调试来测试这七种算法运行的时间长短，从中选择面对不同大小的文件时，哪一种算法更为快捷。软件环境本课程设计所用操作系统为Windows-XP 操作系统，所使用的软件为Microsoft Visual C+6.0；3.详细设计3.1 直接插入排序算法思想：直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到一个已排好序的有序表中，从而得到一个新的、记录数增一的有序表。在自i-1 起往前搜索的过程中，可以同时后移记录。整个排序过程为进行n-1 趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入

7、，直至整个序列变成按关键字非递减有序序列为止。程序实现及核心代码的注释：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;3.2折半排序算法思想：由于折半插入排序的基本操作是在一个有序表中进行查找和插入，这个“查找”操作可利用折半查找来实现，由此进行的插入排序称之为折半插入排序。折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，这般插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。因此，这般插

8、入排序的时间复杂度仍为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+1;-j)r.basej+1=r.basej;/记录后移r.basehigh+1=temp;/插入 名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 33 页 -3.3 希尔

9、排序算法思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。其中，子序列的构成不是简单的“逐段分割”，而是将分隔某个“增量”的记录组成一个子序列。程序实现及核心代码的注释：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+m =r.basej;/记录后移，查找插入位置r.base j+m =temp;/插入 3.4简单选择排序算法思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然

10、后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。程序实现及核心代码的注释：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;/把下标为j 的数与 i 数互换；r.basej=temp;3.5堆排序算法思想：堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。将序列所存储的元素AN 看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二

11、叉名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 33 页 -树：树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。算法的平均时间复杂度为 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

12、.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=m+1;ri=x;/把字符 x 插入到该位置，元素插入实现3.6归并排序算法思想：先将相邻的个数为1 的每两组数据进行排序合并；然后对上次归并所得到的大小为2名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 33 页 -的组进行相邻归并

13、；如此反复，直到最后并成一组，即排好序的一组数据。程序实现及核心代码的注释：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 m)/第一组数据先排完的情况while(j=w)t.base+k=r.basej+;else while(i=m)t.base+k=r.basei+;void tgb(int s,int n,Sq

14、List6 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，也就是余下的数不能凑成/两组，凑一组有余,则把余下的数进行组名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 33 页 -/合，并对其进行排序；merge(r,i,i

15、+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,n,r,t);/s 为每组元素的个数、n 为元素总个数、r/为原数组，t 为待排序的数组，进行归并排s*=2;/序；把元素个数相同的两组合并并进行重新/定义成新的一组，此组元素个数为2*

16、s；if(sn)tgb(s,n,t,r);s*=2;/当元素个数小于n 时，对其进行合并排序；else/当元素个数大于n 时，对剩下的数排序；i=0;while(i=n)r.basei=t.basei+1;i+;3.7冒泡排序算法思想：1、先将一组未排序的数组的最后一个数与倒数第二个数进行比较，并将较小的数放于名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 33 页 -两个数中较前的位置，然后将比较后的较小的数与倒数第三个进行比较，依次比较到第一个数，即可得到第一个数是所有数中最小的数；2、然后再将数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，依次比

17、较到第二个数，3、如此循环到只剩最后两个比较，即得到排好序的一组数。程序实现及核心代码的注释：for(i=0;i=i;j-)/从后往前依次两两比较，较小的被调换到前面；if(r.basej+1 1m 1.5s 0.2s 6.0s 0.1s 3m 5.5s 1.1s 23s 0.1s 0.1s 24s 200KB-20s 3.8s-0.1s 1m 512KB-1m 14s-3m 1024KB-3m 1m-0.2s 0.3s 10m-：表示时间过长6.2结论通过实验结果的比较与分析我们发现：直接插入排序、冒泡排序、简单选择排序及折半插入排序是低效率的排序方式；所以我们实际编程重要尽可能的避免他们的

18、出现；我们应该用较先进的归并排序及堆排序。7.实验心得与分析通过本次课程设计，我们小组的每个成员都学到了很多东西。首先要说的是我们的编程能力，在这一次的课程设计中我们的编程能力均得到了一定程度的提升。并且通过这次课程设计，我们更加熟悉了如何使用Header File 文件。本次课程设计，让我们对于直接插入排序，折半插入排序，希尔排序，简单选择排序，堆排序，归并排序，冒泡排序等七种排序算法的思想有了进一步的认识，同时对七种算法的应用有了更进一步的掌握。通过这次课程设计，我们对于解决实际问题的能力有了进一步提高。最重要的是，这次课程设计大大的训练了我们的小组团队协作能力。通过这次课程设计我们小组各

19、成员的团队协作能力都有了很大的提升。这种团队协作能力对于我们学编程的来说是极其重要的，同时也是必不可少的。当然，我们写程序的时候遇到了很多困难。而且在程序调试过程中出现了很多错误与警告，不过在队员及老师的帮助下均得到了解决。当程序可以运行后，程序的运行过程中同样也也出现了很多错误，甚至出现了不兼容的情况。不过，后来在队员及老师的帮助下也均得到了解决。然而，我们的程序还有一点瑕疵让我们感到美中不足。那就是在归并算法运行过程中，当输入为9 个字符时，排序结果会出现偶然误差。经过分析，我们认为这点是系统的问题。不过，这仍然是一点让我们感到遗憾的地方。名师资料总结-精品资料欢迎下载-名师精心整理-第

20、16 页，共 33 页 -8.附录8.1直接插入排序#include#include#define Q 1000 typedef 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

21、)r.base=r.base-r.length;r.base=(char*)realloc(r.base,(r.stacksize+Q)*sizeof(char);if(!r.base)printf(ERROR);return;名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 33 页 -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 j;-i)r.basei=r.bas

22、ei-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 1000 typedef struct char*base;int stacksize;int length;SqList2;名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 33 页 -void zb(FILE*fp)SqList2 r;int i,j,m,low,high;char temp;r.base=(char*)mal

23、loc(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-;

24、r.base=r.base-r.length;for(i=1;i r.length;i+)temp=r.basei;low=0;名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 33 页 -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.base);fclose(fp);free(r.base);8.3希尔排序#include#include#define

25、Q 1000 typedef struct char*base;int stacksize;int length;SqList3;void xe(FILE*fp)SqList3 r;int i,j,k,m;char temp;名师资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 33 页 -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.ba

26、se=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=0&temp r.basej;j-=m)r.base j+m =r.basej;名师资料总结-精品资料欢迎

27、下载-名师精心整理-第 21 页，共 33 页 -r.base j+m =temp;rewind(fp);fprintf(fp,%s,r.base);fclose(fp);free(r.base);8.4简单选择排序#include#include#define Q 1000 typedef 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

28、.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;名师资料总结-精品资料欢迎下载-名师精心整理-第 22 页，共 33 页 -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.

29、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 Q 1000 typedef struct 名师资料总结-精品资料欢迎下载-名师精心整理-第 23 页，共 33 页 -char*base;int stacksize

30、;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(r.length=(r.stacksize-1)r.base=r.base-r.length-1;r.base=(char*)

31、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-;名师资料总结-精品资料欢迎下载-名师精心整理-第 24 页，共 33 页 -r.base-;r.base=r.base-r.length-1;for(i=r.length/2;i=1;-i)HeapAdjust(r.base,i,r.length);for(i=r.length;i=2;-i)temp=r.base1;r.base1=r.bas

32、ei;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(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)名师资料总结-精品资料欢迎下载-名师精

33、心整理-第 25 页，共 33 页 -ri=rj;i=j;j*=2;else j=m+1;ri=x;8.6归并排序#include#include#define Q 1000 typedef 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=m+1;k=h-1;while(i=m)&(j=w)k+;if(r.basei m)while(j=w)t.base+k=r.basej+;名师资料总结-精品资料欢迎下载-名师精

34、心整理-第 26 页，共 33 页 -else while(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(FILE*fp)SqList6 r;r.length=0;r.base=(char*)malloc(1000*sizeof(char);r.stack

35、size=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;名师资料总结-精品资料欢迎下载-名师精心整理-第 27 页，共 33 页 -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.len

36、gth-;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.baser.length=0;rewind(fp);名师资料总结-精品资料欢迎下载-名师精心整理-第 28 页，共 33 页 -fprintf(fp,%s,r.base);fclose(fp)

37、;free(t.base);free(r.base);8.7冒泡排序#include#include#define Q 1000 typedef 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.stacksize=1000;while(!feof(fp)fscanf(fp,%c,r.base);r.base+;r.length+;if(r.lengt

38、h=r.stacksize)r.base=r.base-r.length;r.base=(char*)realloc(r.base,(r.stacksize+Q)*sizeof(char);if(!r.base)名师资料总结-精品资料欢迎下载-名师精心整理-第 29 页，共 33 页 -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=i;j-)if(r.basej+1 r.basej)temp=r.basej+1;r.

39、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 名师资料总结-精品资料欢迎下载-名师精心整理-第 30 页，共 33 页 -#includexe.h#includejd.h#includemp.h#includedp.h#includegb.h void main()FILE*fp;int sign;while(sign!=0)pr

40、intf(请选择：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:名师资料总结-精品资料欢迎下载-名师精心整理-第 31 页，共 33 页 -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);名师资料总结-精品资料欢迎下载-名师精心整理-第 32 页，共 33 页 -评语：评阅教师签名：年月日成绩名师资料总结-精品资料欢迎下载-名师精心整理-第 33 页，共 33 页 -