1、 数 据 结 构数 据 结 构 课课 程程 设设 计计 姓姓 名：名： 学学 号：号： 学学 部：部： 信息科学与技术学部信息科学与技术学部 专专 业：业： 班班 级级： 题题 目：目： 各种排序算法的设计和分析各种排序算法的设计和分析 教教 师：师： 20132013 年年 0303 月月 0707 日日 - 2 - 一. 课程设计报告的内容课程设计报告的内容 1. 设计题目 2. 运行环境（软、硬件环境） 3. 算法设计的思想 4. 算法的流程图 5. 算法设计分析 6. 源代码 7. 运行结果分析 8. 收获及体会 二. 数据结构 课程设计题目各种排序算法的数据结构 课程设计题目各种排序
2、算法的 设计和分析设计和分析 - 3 - 1. 设计题目 （1 1） 、需求分析、需求分析 利用随机函数产生 N 个随机整数（N=4000） ，利用直接插入排序、折 半插入排序，起泡排序、快速排序、选择排序、堆排序，基数排序七种排 序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序） ，并统 计每一种排序所耗费的时间。把排序花的时间排在表格里面。 （2） 、程序的主要功能、程序的主要功能 1.用户输入任意个数，产生相应的随机数 2.用户可以自己选择排序方式（直接插入排序、折半插入排序、起泡排 序、快速排序、选择排序、堆排序、基数排序）的一种 3.程序给出原始数据、 排序后从小到大的数据
3、， 并给出排序所用的时间。 （3） 、程序运行平台、程序运行平台 Visual C+ 6.0 版本 （4） 、数据结构数据结构 （5） 、算法及时间复杂度） 、算法及时间复杂度 （一）各个排序是算法思想：（一）各个排序是算法思想： （1）直接插入排序：将一个记录插入到已排好的有序表中，从而得到一个 新的，记录数增加 1 的有序表。 （2）折半插入排序：插入排序的基本插入是在一个有序表中进行查找和插 入，这个查找可利用折半查找来实现，即为折半插入排序。 （3）起泡排序：首先将第一个记录的关键字和第二个记录的关键字进行比 较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记 录的关键字。依
4、此类推，直到第 N-1 和第 N 个记录的关键字进行过比 较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到 最后一个记录的位置上。然后进行第二趟起泡排序，对前 N-1 个记录 进行同样操作。一共要进行 N-1 趟起泡排序。 （4）快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部 分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分 记录继续进行排序，已达到整个序列有序。 （5）选择排序：通过 N-I 次关键字间的比较，从 N-I+1 个记录中选出关键 字最小的记录，并和第 I（1next=s; q=s; t+; q-next=NULL; d=1; while(n0) for(j=0;jkey/d; k=k%
