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

课 程 设 计 报 题 目： 排序综合

院 系： 计算机科学与应用 专业年级： 12级计科

学 号： 121096124 学生姓名： 平宁宁 指导老师： 薛海燕

2013年6月10日

告

目录

一.设计任务书 ................................................................................................................................. 2

1.1题目与要求 ........................................................................................................................ 2 1.2设计知识点 ........................................................................................................................ 2 1.3预期目标 ............................................................................................................................ 2 二．概要设计 ................................................................................................................................... 2

2.1各种排序算法的特点 ........................................................................................................ 2

2.1.1冒泡排序 .................................................................................................................. 2 2.1.3简单选择排序 .......................................................................................................... 3 2.1.4快速排序 .................................................................................................................. 3 2.1.5 希尔排序 ................................................................................................................. 3 2.1.6 堆排序 ..................................................................................................................... 3 2.2各种算法的比较方法 ........................................................................................................ 4

2.2.1 稳定性比较 ......................................................................................................... 4 2.2.2 时间复杂性比较 ................................................................................................. 4 2.2.3 辅助空间的比较 ................................................................................................. 4 2.2.4 其它比较 ............................................................................................................. 4

三.详细设计 ..................................................................................................................................... 4

3.1 流程图 ............................................................................................................................... 4 3.2流程图模块说明 ................................................................................................................ 5 3.3可排序表的抽象数据类型定义 ........................................................................................ 5 3.4程序代码 ............................................................................................................................. 6

3.4.1 函数声明 ............................................................................................................... 6 3.4.2 六种排序算法代码 ............................................................................................. 8 3.4.3 排序算法选择 ................................................................................................... 13 3.4.4 主函数程序代码 ............................................................................................... 15

四.调试分析 ................................................................................................................................... 19

4.1调试分析 .......................................................................................................................... 19 4.2输入输出 .......................................................................................................................... 19 4.3排序算法评价 .................................................................................................................. 23 4.4经验和体会 ...................................................................................................................... 23 五．参考文献 ................................................................................................................................. 24 六.致谢........................................................................................................................................... 24

一.设计任务书

1.1题目与要求 题目：排序综合

要求：利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行

排序。 要求：

1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。 2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。

3)如果采用4种或4种以上的方法者，可适当加分。

1.2设计知识点

1）本演示程序对以下6种常用的内部排序算法进行实测比较：冒泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序；

2）待排序表的元素的关键字为整数。比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）；

3）演示程序以以用户和计算机的对话方式执行，在计算机终端上显示提示信息，对随机数组进行排序，并输出比较指标值；

4）最后对结果作出简单分析。

1.3预期目标

按要求输入不同的操作。输入后，根据不同的输入进行不同的操作，最终达到对各算法进行比较的目的。通过此次课程设计主要达到以下目的了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

二．概要设计

2.1各种排序算法的特点 …… 此处隐藏：11113字，全部文档内容请下载后查看。喜欢就下载吧 ……