《数据结构算法课程设计-排序算法的实现》由会员分享，可在线阅读，更多相关《数据结构算法课程设计-排序算法的实现（25页珍藏版）》请在金锄头文库上搜索。
1、河南工程学院数据结构与算法课程设计成果报告排序算法的实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目排序算法的实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导
2、教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务12 分析与设计22.1 题目需求分析22.2 存储结构设计42.3 算法描述42.4 程序流程图72.5 测试程序说明73 程序清单84 测试134.1 测试数据134.2 测试结果分析135 总结14参考文献151 课程设计目标与任务1.1 课程设计目标数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各方面
3、得到锻炼：1.能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；2.通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；3.培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；4.尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来，获得算法的直观感受 。1.2 课程设计任务本演示程序用c语言编写，完成各种排序的实现，对输入的一组数字实现不同的排序方法，并把排序结
4、果进行保存。1.编写程序算法，产生20000个随机数。2.分别对直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序等算法进行编写。3.通过题目要求的排序方法对这20000个随机数进行排序，并保存其结果。4.程序所能达到的功能：产生20000个随机数，并通过各种排序方法对它们进行排序。2 分析与设计2.1 题目需求分析1.直接插入排序：插入排序的基本思想是每步将一个待排序的记录按其排序码值的大小，插到前面已经排好的文件中的适当位置，直到全部插入完为止。插入排序方法主要有直接插入排序和希尔排序。直接插入排序具体算法描述如下：（1） 从第一个元素开始，该元素可以认为已经被排序（2
5、）取出下一个元素，在已经排序的元素序列中从后向前扫描（3）如果该元素（已排序）大于新元素，将该元素移到下一位置（4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置（5） 将新元素插入到下一位置中（6） 重复步骤。2.折半插入排序：折半插入排序是对直接插入排序的简单改进，对于直接插入排序而言，当第i-1趟需要将第i个元素插入前面的0i-1个元素序列中时，总是需要从i-1个元素开始，逐个比较每个元素，直到找到它的位置。这显然没有利用前面0i-1个元素已经有序这个特点，而折半插入排序则改进了这一点。对于折半插入排序而言，当需要插入第i个元素时，它不会逐个进行比较每个元素，而是：（1）计算0
6、i-1索引的中间点，也就是用i索引处的元素和(0+i-1)/2索引处的元素进行比较，如果i索引处的元素值大，就直接在(0+i-1)/2i-1半个范围内进行搜索；反之在0(0+i-1)/2半个范围内搜索，这就是所谓的折半；（2）在半个范围内搜索时，按照（1）的方法不断地进行折半搜索，这样就可以将搜索范围缩小到1/2、1/4、1/8，从而快速的确定插入位置。3.希尔排序：希尔(Shell)排序的基本思想是：先取一个小于n的整数d1作为第一个增量把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取得第二个增量d2d1重复上述的分组和排序，直至所
7、取的增量di=1，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。一般取d1=n/2，di+1=di/2。如果结果为偶数，则加1，保证di为奇数。4.起泡排序：冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，
8、大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。5.快速排序：快速排序采用了一种分治的策略，通常称其为分治法，其基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。快速排序的具体过程如下：第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录分成两组，第1组各记录的排序码都小于等于该排序码，第2组各记录的排序码都大于该排序码，并把该记录排在这两组中间。第二步，采
9、用同样的方法，对左边的组和右边的组进行排序，直到所有记录都排到相应的位置为止。6.简单选择排序：选择排序的基本思想是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。选择排序中主要使用直接选择排序和堆排序。直接选择排序的过程是：首先在所有记录中选出序码最小的记录，把它与第1个记录交换，然后在其余的记录内选出排序码最小的记录，与第2个记录交换.依次类推，直到所有记录排完为止。2.2 存储结构设计此程序采用的是线性表的动态顺序存储结构：#define LIST_INIT_SIZE 100/线性表存储空间的初始分配量#define L
10、ISTINCREMENT 10/线性表存储空间的分配增量Typedef structElemType *elem;/存储空间基址Int length;/当前长度Int listsize;/当前分配的存储容量（以sizeof(ElemType)为单位）SqList;上述定义中，数组指针elem指示存储空间基址，length表示线性表的当前长度，对线性表的初始化操作就是为顺序表预定义大小的数组空间，并将线性表的当前长度设为“0”，listsize指示当前分配的存储空间大小，一旦元素插入而空间不足，可进行再分配。2.3 算法描述1.直接插入排序：void InsertSort(RecType R,i
11、nt length) / 对数组a作直接插入排序 int i,j; for(i=2;i=length;+i) if(Ri.keyRi-1.key) / 需将ai插入有序子表 R0.key=Ri.key; / 复制为哨兵 Ri.key=Ri-1.key; for(j=i-2;R0.keyRj.key;-j) Rj+1.key=Rj.key; / 记录后移 Rj+1.key=R0.key; / 插入到正确位置 2.折半插入排序：void BInsertSort (RecType R,int low,int high,int length) int m; for ( int i=2; i=lengt
12、h; +i ) R0.key = Ri.key; / 将Ri暂存到R0 low = 1; high = i-1; while ( low = high) /在Rlow.high中折半查找插入的位置 m = (low+high)/2; / 折半 if (R0.key =high+1; -j ) Rj+1.key = Rj.key; / 记录后移 Rhigh+1.key = R0.key; / 插入 / BInsertSort3.希尔排序：void ShellSort(RecType R,int n)/*希尔排序算法*/int i,j,d,k;RecType temp;d=n/2;/*d取初值n/2*/while (d0) for (i=d;i=0 & Rj.keyRj+d.key) temp=Rj; /*Rj与Rj+d交换*/Rj=Rj+d;Rj+d=temp;j=j-d;printf( d=%d: ,d);/*输出每一趟的排序结果*/for (k=0;kn;k+)printf(%3d,Rk.key);printf(n); d=d/2; /*递减增量d*/4.起泡排序：void bubble_sort(RecType R,int length) / 将a中整数序列重新排列成
