《数据结构》课程设计报告--排序综合.doc

数据结构 课程设计报告 设计题目：排序综合 年 级 班 级 姓 名 学 号 指导教师 起止时间 年 学期 一．实习目的 通过实习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。 二．问题描述（具体任务） 利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。 要求： 1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。 2 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。 3 如果采用4种或4种以上的方法者，可适当加分。 具体任务： 分别实现直接插入、直接选择、冒泡、快速排序、堆排序的算法。从时间的角度来分析各种排序的性能。通过测试多组数据来掌握各种排序的方法及适用场合，并能在解决实际问题灵活运用。在编写代码的时候，有以下几个问题： 建立一个主函数，在主函数中要有菜单界面，和输入功能键相应执行的功能。并且要求能循环适用系统。 分别实现直接插入、直接选择、冒泡、快速排序、堆排序的算法。 通过冒泡排序法来测试每组数据用哪种排序算法最优。 三．需求分析 1）本演示程序对以下7种常用的内部排序算法进行实测比较：直接插入排序、直接选择排序、冒泡排序、快速排序、堆排序、希尔排序、归并排序。 2） 3）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”下，用户可由键盘输入选择以何种算法进行排序，测试数据可由用户自行输入或由系统产生随机数。每次测试完毕，将显示该排序的排序时间。 4）选择一键排序比较功能，测试完毕，列表显示各种算法的排序时间。并且对结果做出简单分析，给出排序时间最短的两种排序算法。 四．算法设计思想及流程图 五．C语言源代码 #include #include #include #include #include #define N 21000 //按键不符时提示 void Wrong printf \n 按键错误!\n ; getchar ;//getchar 函数从STDIN 标准输入 获取并返回下一个字符,如果到达文件尾返回EOF //显示排序结果 void Disp int a[] int i; system cls ; //清屏 for i 0;i N;i++ if i-1 %10 9 printf \n ; printf %-7d,a[i] ; //插入排序 void InsertSort int a[] int i,j,temp; for i 1;i N;i++ temp a[i]; //操作当前元素，先保存在其他变量中 for j i;j 0a[j-1] temp;j-- // 从当前元素的上一个元素开始查找合适的位置 a[j] a[j-1]; a[j] temp; //选择排序 void SelectSort int a[] int i,j,k; for i 0;i N-1;i++ k i; for j i+1;j N;j++ //从j 往前的数据都是排好的，所以从j 开始往下找剩下的元素中最下的 if a[j] a[k] k j; if k! i int temp; temp a[k]; a[k] a[i]; a[i] temp; //冒泡排序算法 void BubbleSort int a[] int i,j,temp; for i 0;i N-1;i++ for j N-1;j i;j-- //比较,找出本趟最小关键字的记录 if a[j] a[j-1] temp a[j]; //进行交换,将最小