数据结构课程设计—排序综合

《数据结构课程设计—排序综合》由会员分享，可在线阅读，更多相关《数据结构课程设计—排序综合（20页珍藏版）》请在装配图网上搜索。

1、攀枝花学院本科学生课程设计任务书题目排序综合1、课程设计的目的1）使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操 作实现算法，以及它们在程序中的使用方法。2）使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。2、课程设计的内容和要求（包括原始数据、技术要求、工作要求等）问题描述：用程序实现多种排序算法基本要求：利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法 进行排序。要求：1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序

2、、希尔排序、 起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在 不同的文件中。2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出 其中两种较快的方法。如果采用4种或4种以上的方法者，可适当加分。3、主要参考文献1刘大有等，数据结构（C语言版），高等教育出版社2严蔚敏等，数据结构（C语言版），清华大学出版社3William Ford，William ToppData Structure with C+清华大学出版社4苏仕华等，数据结构课程设计，机械工业出版社4、课程设计工作进度计划第1天完成方案设计与程序框图第2、3天编写程序代码第4天程序调试分

3、析和结果第5天课程设计报告和总结指导教师（签字）日期年 月 日教研室意见：年 月 日学生（签字）：接受任务时间：年 月曰注：任务书由指导教师填写。课程设计（论文）指导教师成绩评定表合 宗 纟 序 -三分值得分工 作 表 现 20%度 态 习*n口做计 试戕 实与 过取 通获量n能35%能出 题得 匕匕汉 厶冃能 技， 和据 识数。 知验论 学实结 所理的 用处值 运确价 匕匕E 一 nr 厶冃J杀5Ld自心 并的案方九 匕匕厶冃(匕匕厶冃 计计 设设Ldn、 、 试晰 调清、路 装思 置研 磧氧0吟熱 能操完3*斤术 価技 果匕匕E7厶冃 湃析7) 验分功 、买合能 做综噺/|计力济 寸匕匕u

4、 厶冃么二o1AO 力 匕匕 厶冃 的 合 宀示成果质量45%鳳度n文 本 合量n整； 完理 练合 简谨 述严 综论新 创n指导教师评语日 月 年 导 指摘要排序（sorting ）是计算机程序设计的一种重要操作，他的功能是将一个数据元素（或记录）的任意序列，重新排列一个按关键字有 序的序列。由于待排序的记录数量不同，使得排序过程中涉及的储存 器不同，可将排序方法分为两大类：一类是内部排序，指的是待排序 记录存放在计算机随机储存器中进行的排序过程；另一类是外部排序 指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在 排序过程中尚需对外存进行访问的排序过程。内部排序又分为：插入排序、快

5、速排序、选择排序、归并排序 和基数排序。其中插入排序又分为：直接插入排序、其他插入排序和 希尔排序；选择排序分为：简单选择排序、树形选择排序和堆排序； 基数排序又分为：多关键字的排序和链式基数排序。本次课程设计就是内部排序中的几个排序方法。关键字： 内部排序 关键字 重新排列一、方案设计(1)、程序的模块1、输入2、选择3、输出(2)、模块的功能1、输入模块的功能：利用随机函数产生N个数(超过20000),由于产生的 数较多，不好查看排序后的顺序是否正确，所以在本程序中只随机产生20个数。create(a,b,&n) 是一个随机函数，它可以随机产生20个随机数 。2、选择模块的功能：选择数字则

6、进行对应的排序；选择字母则进行重新产 生随机数和退出的操作。1 插入排序insertsort(a,n)2 希尔排序xiersort(a,n)3 冒泡排序 maopaosort(a,n)4 快速排序 quicksort(a,1,n)5 简单排序 jiandansort(a,n)6堆排序duisort(a,n)C(c)重新产生20个随机数create(a,b，&n)N(n)退出程序3、输出模块的功能：把利用各种排序方法排好顺序的数输出到一个文件夹 中。writefile1(a,n)向指定的文件中写入排序前的数writefile2(a,n)向指定的文件中写入用各种排序方法排好序的数二、程序操作过程图

7、开始输入字母，选择重 新置数或者是退出输入数字，选 择排序方法C (c) 退出把利用排序方法排好序的数 输出到指定的文件夹利用随机函数产 生20个随机数N(n)重新产 生随机 数2希尔 排序1插入 排序4 快速 排序3 冒泡 排序5简单 排序6 堆 排序三、程序流程图开始C重 产 随 数6堆 排 序输入数字或者字母，选 择排序方法或其他(c)新生机把用各种排序方法排 好的数的顺序输出到 匕指定的文件夹中利用随机函数产 生20个随机数2希尔 排序1插入 排序4 快速 排序3 冒泡 排序N(n)退 出5简单 排序四、程序源代码#include#include#include#define M 20

8、/*把排序之前的数输入到指定文件夹中*/Void writefile1(int *a,int n) FILE *fp;int i;char filename10;prin tf(请输入要输出的文件名称(包括后缀名)：n);gets(filename);if(fp=fopen(filename,w)=NULL)fprin tf(不能打开文件！n);fprin tf(“ 排序之前 ：*n);for(i=1;i=n;i+)fprintf( %3d,ai);/*把用各种排序方法排序后的数输入到指定文件夹中*/void writefile2(int *a,int n) FILE *fp;int i;ch

9、ar filename10;fprin tf(请输入要输出的文件名称(包括后缀名)：n);gets(filename);if(fp=fopen(filename,w)=NULL)fprin tf(不能打开文件！n);prin tf(“ 排序之后：*n);for(i=1;i=n;i+)printf( %3d,ai);a0=-1;/*用随机函数产生20个随机数*/void create(int *a,int *b,int *n) int i,; srand(unsigned)time(NULL); for(i=0;in;i+) ai=rand();bi=ai;printf(%8d ,ai); /*

10、1*插入排序*/void insertsort(int *a,int n) int i,j;for(i=2;i=n;i+) a0=ai; for(j=i-1;a0aj;j-) aj+1=aj;aj+1 =a0; /*插入排序*/*2*希尔排序*/void xiersort(int *a,int n) int d3=5,3,1;int i,j,k=0;while(k3) for(i=dk+1;i0&aja0;j=j-dk)aj+dk=aj;aj+dk=a0;k+; /*希尔排序*/*3*冒泡排序*/void maopaosort(int *a,int n) int i,j,change,t;fo

11、r(i=1;in;i+) change=0;for(j=1;jaj+1) t=aj; aj=aj+1;aj+1=t; change=1;if(change=0)break; /* *冒泡排序* */*4*快速排序 */ void quicksort(int *a,int t, int n) int i=t,j=n;while(ij) if(ij) a0=ai;while(ia0)j-;if(ij) ai=aj; i+; while(ij&aia0) i+;if(ij) aj=ai; j-; ai=a0;quicksort(a,1,i-1); quicksort(a,i+1,n); /*快速排序

12、*/*5*简单排序 */ void jiandansort(int *a,int n) int i,j,t;for(i=1;in;i+) for(j=i+1;jaj) t=ai;ai=aj;aj=t;/*简单排序*/*6*堆排序*/void adjust(int *a,int low, int top) int j;a0=alow;for(j=2*low;j=top;j*=2) if(jaj+1)j+;if(aj0;i-)adjust(a,i,n);for(i=n;i1;-i)printf(%5d,a1)a1=ai;adjust(a,1,i-1);printf(%5d,ai);/*堆排序*/

13、void main( )int aM+1,bM+1,n=0,i;char ch1=y,ch2; create(a,b,&n);while(ch1=y|ch1=Y) printf(n 输入 1 插入排序);printf(n输入2希尔排序)；printf(n输入3冒泡排序)；printf(n输入4快速排序)；printf (n 输入5简单排序)；printf (n 输入6堆排序)；printf(n输入C(c)重新产生随机数);printf(n 输入 N(n)退出n);scanf(n%c,&ch2)；if(a0=-1)for(i=1；i=n；i+)ai=bi；switch(ch2) case1: w

14、ritefile1 (a,n);insertsort(a,n) ;writefile 2(a,n);break;case2:writefile 1(a,n);xiersort(a,n);writefile 2(a,n);break;case3:writefile 2(a,n);maopaosort(a,n);writefile 2(a,n);break;case4:writefile 1(a,n);quicksort(a,1,n);writefile 2(a,n);break;case5:writefile 1(a,n);jiandansort(a,n);writefile 2(a,n);br

15、eak;case6:writefile 1(a,n);duisort(a,n) ;writefile 2(a,n);break;caseC:casec:create(a,b,&n); break;caseN:case n :ch1=n; 五、程序调试分析和结果(1)、运行程序，程序利用随机函数产生20个数，选择“1”，进行插入排序；在选择“2”, 进行希尔排序，实验过程截图如下：2QBS7 70212G23232351674513745183543234235502929981S97G51S1315378497242505Q614228输.插八屮序输.2弄匚:1E序mA 3冒泡匸；丽/.4快速

16、屮序iii/5茴旦屮序输A右堆排序输人亡“、重新产生騎机数输入瞅2退出1-青輸人要揄出的文件名和f包括百绑兽兀：L就肚非序插入排序输丸玄希尔排序输.A, s冒泡T游諭A 4快速排序输人5简单厂諭.Jd乍排序諭Aco畫轿生随机数非序諭An退出AAAAAAAA数n 序序序序序生 -y -1- 2-1匚2-1匚J-I=I,-IJ-I,=卜J-I=IH亠-亠严 幫里排抵匕7058)1487(2)、打开“l.txt”文件和“2.txt”文件，查看实验结果。iiiTlJj wlj=) r&xll.U.l 查三(V)毎助止0排序之前1* 1*1jh.2033770212623232-516745丄芮4518

17、3t54亞3Eu51 TuES5029395218976E15131E27S4C7 243502088770212623232-5U74E1374518354323E06170E82255029398818976E15131E2784S7 2435043 匪 14E7排序之后:才*才*1487323539884225432:43285C29E06151E17C21705SS49713745lf-74E18365ISC-76 2CSS7 L-13E026L3231527卜：5)、选择“5”，进行简单排序；在选择“6”，进行堆排序，实验过程截图如下：C:UsersAd n i riistratcr

18、Oe skto pDet ug7. exeIU,回(6)、打开“5.txt”文件和“6.txt”文件，查看实验结果。:ff哼偿哼 ntlHTP-亠寸亠 入爪泡速单申新出 ffi希冒快简堆童遍输入1帝入排序输1人2希尔排序Ki A 3冒泡舫瞌人4快養惊输人5简单排序揄.入毎徘疥SiiAc董新产生隔机数嶽入N5退山6请输入要输出的文件名称f包括后给名、.txt5.txt 文件的截图：6.txt 文件的截图：六、各种排序算法的性能分析由于程序不能统计出运行各种算法所需要的时间，所以在本程序中以各种算 法的时间复杂度来分析各种算法的性能。1. 插入排序：算法的时间复杂度为：0(n*n)2. 希尔排序：

19、算法的时间复杂度为n的1.2次幂3. 冒泡排序：这是最原始，也是众所周知的最慢的算法了。他的名字的由 来因为它的工作看来象是冒泡。算法的时间复杂度为：0(n*n)。当数据为正序，将不会有交换，复杂度 为 0(0)。4. 快速排序：算法的平均时间复杂度为：Iog2(n)*n,所有内部排序方法 中最好的，大多数情况下总是最好的。5. 简单排序：算法的时间复杂度为：0(n*n)6. 堆排序：算法的时间复杂度为：Iog2(n)*n综上：由各种算法的时间复杂度比较可知，堆排序和快速排序是渐进最优的 排序算法。七、总结1、插入排序(I nsertSort)插入排序通过把序列中的值插入一个已经排序好的序列中

20、，直到该序列的结束。插入排 序是对冒泡排序的改进。它比冒泡排序快2 倍。一般不用在数据大于1000的场合下使用插 入排序，或者重复排序超过200 数据项的序列。2、Shell 排序(ShellSort)Shell 排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行 一次插入排序，以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会 对算法产生重要的影响。现在多用D.E.Knuth的分组方法。Shell 排序比冒泡排序快 5 倍，比插入排序大致快 2 倍。 Shell 排序比起 QuickSort， MergeSort， HeapSort 慢很多。但是它

21、相对比较简单，它适合于数据量在5000 以下并且速度 并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。3、冒泡排序( BubbleSort)冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地 比较数组中的每一个元素，使较大的数据下沉，较小的数据上升。它是0(2 )的算法。4、快速排序( QuickSort)快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排 序的就地版本。快速排序可以由下面四步组成。(1) 如果不多于1 个数据，直接返回。(2) 一般选择序列最左边的值作为支点数据。(3) 将序列分成2部分，一部分都大于支点数据

22、，另外一部分都小于支点数据。(4) 对两边利用递归排序数列。快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序 快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有 限的机器来说，它不是一个好的选择。5、简单排序( SimpleSort)简单排序的效率是O(n2)。在实际应用中处于和冒泡排序基本相同的地位。它们只是排序算法发展的初级阶段，在实际中使用较少。6、堆排序( HeapSort)堆排序适合于数据量非常大的场合（百万数据）。堆排序不需要大量的递归或者多维的 暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排

23、序， 归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后 一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。八、心得体会说实话，本次做数据结构课程设计，时间非常紧，在课间我做的很少，基本上都 是在课后把本次课程设计做出来的。我们的课程设计安排在16周的下午去做。但是在16周的星期1、2 的上午和星 期 4 的下午我都有考试，因此在星期 1 的上午的考试结束后，在下午的课程设计的课 上我都在复习第二天要考试的内容；而在星期2 上午考试结束后，星期 2 下午和星期 三我都在

24、复习星期4要考试的内容。所以，我从星期1 到星期4的课程设计课我基本 上什么也没有做。我真正开始做课程设计是从星期5 上午在寝室开始的。做了星期 5 一天，我才把方案设计、程序操作过程、程序流程图和很少一部分程 序源代码做好，然后在寝室从星期6、星期天到17周星期 1整整3 天才把所有内容 都写完。然后星期 2 花了一整天的时间才整理出来这个课程设计的论文。写完后，我心里有两个感受：第一是：累！我差不多花了整整5 天时间来写这个 课程设计，在这其间，我只有在吃饭的时候看会儿电视，其余的时候我基本上都在做 课程设计（睡觉的时间除外）。第二是：满足！这个课程设计是我从搜集资料、整理 资料、到写好这份课程设计都是我一个人完成的，绝没有抄袭别人的。通过这次课程设计，我收获颇多。原来上课时没有听懂的地方，通过这次课程设 计，我自己翻书，查资料，我基本上都理解了；原来疑惑的地方现在也明白了！