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

1、精选优质文档-倾情为你奉上专心-专注-专业 东华理工大学东华理工大学课程设计报告课程设计报告课程设计题目：课程设计题目： 综合排序的设计综合排序的设计学生姓名：何杨学生姓名：何杨班班 级：级：专专 业：信息与计算科学业：信息与计算科学指导教师：郭树蕻指导教师：郭树蕻 2014 年年 12 月月 13 日日精选优质文档-倾情为你奉上专心-专注-专业 目录目录摘要.一、题目的内容及要求-4二、需求分析-4三、概要设计-5四、四种排序源代码详细设计-5五、程序输出的结果-10六、运行结果及分析-12七、收获及体会-13八、参考文献-14精选优质文档-倾情为你奉上专心-专注-专业摘 要数据结构是由数据

2、元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。 排序算法是数据结构学科经典的内容，其中内部排序现

3、有的算法有很多种，其中包含冒泡排序，直接插入排序，简单选择排序，希尔排序，快速排序，堆排序等，各有其特点。对排序算法比较的分析可以遵循若干种不同的准则，通常以排序过程所需要的算法步数作为度量，有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间，例如，当键是较长的字符串时，常以键比较次数作为排序算法计算时间复杂性的度量。当排序时需要移动记录，且记录都很大时，还应该考虑记录的移动次数。究竟采用哪种度量方法比较合适要根据具体情况而定。在下面的讨论中我们主要考虑用比较的次数作为复杂性的度量。关键字：数据结构；算法比较；比较次数；时间复杂度数据结构；算法比较；比较次数；时间复杂

4、度精选优质文档-倾情为你奉上专心-专注-专业一、题目的内容及要求一、题目的内容及要求排序综合排序综合利用随机函数产生 N 个随机整数（20000 以上） ，对这些数进行多种方法进行排序。要求：(1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序） 。并把排序后的结果保存在不同的文件中。(2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比） ，找出其中两种较快的方法。(3)如果采用 4 种或 4 种以上的方法者，可适当加分。二、需求分析二、需求分析2.1 问题描述问题描述 此次的任务要求是输入 20000

5、 个以上的随机整数，对这些数进行多种方法进行排序。（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。 约束：程序可由用户自行设定排序数的个数，但排序数具体值需要由计算机生成，然后用三种以上的排序方法对随机数组进行排序，每一种排序方法执行后需统计出数据移动次数以判断排序方法的对比随机数组的执行优劣性。另：用户自行算出每一种排序方法的时间复杂度与空间复杂度。 2.2 基本要求基本要求2.2.1 输入的形式和输入值的范围；设定的随机数据的范围为 20000 以上，用户自定义随机数的个数n，随机数的数据类型均为整形。2.2.2 输出的形式；程序是以一个完整的有

6、序数组来进行输出。2.2.3 程序所达到的功能：将一个无序数组进行排序随机生成 20000 以上个随机整数，对这些数进行多种方法进行排序。分别采用以下方法实现上述问题求解（可精选优质文档-倾情为你奉上专心-专注-专业采用的方法有简单排序、希尔排序、冒泡排序、快速排序这四种排序方法）。三、概要设计三、概要设计3.13.1 可排序表的抽象数据类型定义：可排序表的抽象数据类型定义：typedef int KeyType; /关键字为整型typedef int OtherType; /关键字为整型typedef structKeyType key; /关键字为 KeyType 型OtherType o

7、ther_data;RecordType; /定义一个 RecordType 型结构体，存放关键字void quicksort(RecordType a,int left,int right)/快速排序void bubbleSort(RecordType a,int length)/冒泡排序void shellSort(RecordType a,int n)/希尔排序void BinSort (RecordType r, int length)/折半插入排序void main()/主函数运行入口四、四种排序源代码详细设计：四、四种排序源代码详细设计：4.1 快速排序模块：快速排序模块：void

8、 quicksort(RecordType a,int left,int right)RecordType t;int i,j,temp; if(leftright) return; temp=aleft.key; i=left; j=right; while(i!=j) while(aj.key=temp & ij)精选优质文档-倾情为你奉上专心-专注-专业 j-; while(ai.key=temp & ij) i+; if(ij) t=ai; ai=aj; aj=t; aleft = ai; ai.key = temp; quicksort(a,left,i-1);/继续处理左边的，这是

9、一个递归的过程 quicksort(a,i+1,right);/继续处理右边的，这是一个递归的过程 /* 快速排序算法 */ 4.2 冒泡排序模块：冒泡排序模块：/此处是一次冒泡排序过程，在主函数中会通过循环调用此冒泡函数过程void bubbleSort(RecordType a,int length)int i,temp; for(i=1;iai+1.key) temp = ai.key; ai.key=ai+1.key; ai+1.key=temp; /* 冒泡排序算法 */ 4.3 希尔排序模块：希尔排序模块：void shellSort(RecordType a,int n)int

10、i, j, temp; int gap = 0;while (gap 0) for ( i = gap; i = 0 ) & ( aj+1.key temp )aj + gap+1.key = aj+1.key;j = j - gap;aj+gap+1.key = temp;gap = ( gap - 1 ) / 3; 4.4 希尔折半插入排序模块：希尔折半插入排序模块：/*折半插入排序法*/void BinSort (RecordType r, int length)/*对记录数组 r 进行折半插入排序，length 为数组的长度*/int i,j;RecordType x;int low,

11、high,mid;for ( i=2; i=length ; +i ) x= ri;low=1; high=i-1;while (low=high ) /* 确定插入位置*/ mid=(low+high) / 2;if ( x.key= low; -j ) rj+1= rj; /* 记录依次向后移动 */ rlow=x; /* 插入记录 */ 精选优质文档-倾情为你奉上专心-专注-专业/*BinSort*/4.5 主函数模块：主函数模块：void main()int n,i,j,t; char b; bool q=false;RecordType a40000; while(1) printf

12、(nn);printf( * 综 合 排 序*nn); printf( *菜 单*nn); printf( * = * n); printf( * 1. 读 取 待排序长度 * n); printf( * 2. 产生随机数并输出 * n); printf( * 3. 采用快速排序法排序 * n); printf( * 4. 采用冒泡排序法排序 * n); printf( * 5. 采用希尔排序法排序 * n); printf( * 6. 采用折半插入排序法排序 * n); printf( * 7. 输 出 * n);printf( * 0. 退 出 系 统 * n);printf( * - *

13、 n); printf( 请输入你要进行的操作); b = getch(); switch(b) case 1: printf(%cn,b);精选优质文档-倾情为你奉上专心-专注-专业printf(请输入待排序记录的长度：);scanf(%d,&n);break; case 2:printf(%cn,b);srand( (unsigned)time( NULL );printf(下面随机生成%d 个数字存储在数组中n,n);for(i=1;i=n;i+)ai.key = rand()%20000;printf(%dt,ai.key);if(i%100=0)printf(n);printf(n)

14、;break;case 3:printf(%cn,b);printf(n-快速排序结束-nn);quicksort(a,1,n);q=true;break;case 4:printf(%cn,b);for(i=0;in-1;i+)bubbleSort(a,n-i);printf(n-冒泡排序结束-nn);q=true;break; case 5:printf(%cn,b);printf(n-希尔排序结束-nn);shellSort(a,n);q=true;break; case 6:printf(%cn,b);BinSort(a,n);printf(n-折半插入排序结束-nn);q=true;

15、break; 精选优质文档-倾情为你奉上专心-专注-专业case 7:printf(%cn,b);if(q)printf(n-排序后输出-n);for(i=1;i=n;i+)printf(%dt,ai.key);if(i%100=0)printf(n); elseprintf(n * = * n); printf( * 您未对待排序数据排序 * n); printf( * 请重新选择排序的序号 * n); printf( * - * n);break; case 0:printf(%cn,b);printf(n 感谢使用综合排序程序n 按任意键退出.n);return;break; defau

16、lt:printf(输入错误请重新输入nn); 五、程序输出的结果：五、程序输出的结果：5.1 输入和输出：输入和输出：(1)主函数运行的输出结果：精选优质文档-倾情为你奉上专心-专注-专业(2)选择 1，读取待排序长度（这里以 20000 为例）：(3)选择 2，产生随机数并输出：(4)选择 3，采用快速排序法排序：精选优质文档-倾情为你奉上专心-专注-专业（选择 4、5、6 的其他排序法的输出雷同，此处就不再重复）(5)选择 7，输出排序结果：六、运行结果及分析六、运行结果及分析6.1 各算法的比较方法各算法的比较方法1.稳定性比较 折半插入排序、冒泡排序是稳定的 希尔排序、快速排序是不稳

17、定的2.时间复杂性比较 折半插入排序、冒泡排序的时间复杂性为 O(n2) 其它非线形排序的时间复杂性为 O(nlog2n)3.辅助空间的比较精选优质文档-倾情为你奉上专心-专注-专业 线形排序的辅助空间为 O(n),其它排序的辅助空间为 O(1);4.其它比较插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。反而在这种情况下，快速排序反而慢了。当 n 较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。当 n 较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。七、收获及体会七、收获及体会根据四种排序法的基础理论实际性模仿和编写算

18、法程序，很是困难，算法是程序的灵魂，数据结构确是算法的基础，但是不断的实践也是一种进步的好途径。这次课程设计主要是对基础知识的灵活应用，这就让我进一步提高了对数结构知识的巩固。这次设计的完成，困难是少不了的，还有很多其它的难题让我都不知道所措，但是通过努力最终解决他们让我体会到成就感，更重要的是我的能力在实践中得到了提升和优化，特别是对常用的排序算法的应用，这对我以后从事软件应用程序开发是有很大的帮助的。这次课程设计的心得体会通过实习我的收获如下 1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程