数据排序C程序设计课程设计报告.doc

淮阴工学院 C++程序设计课程设计报告 选题名称: 数据排序 系（院）: 专 业: 班 级: 姓 名: 学 号: 指导教师: 学年学期: 2015 ~ 2016 学年 第 2 学期 2016 年 6 月 28 日  摘要： 排序是数据处理中经常使用的一种重要运算。设文件由n个记录{R1，R2，……，Rn}组成，如n个学生记录，每个学生记录包括学号、姓名、班级等。n个记录对应的关键字集合为{K1，K2，……，Kn}，如学生的学号。所谓排序就是将这n个记录按关键字大小递增或递减重新排列。 当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。内部排序方法可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。个基本的操作：关键字大小移动记录本身改变指向记录的指针。目 录 1 课题需求描述1 1.1 课题来源 1 2 总体设计 2 2.1总体方案 2 3详细设计与实现4 3.1插入排序 4 3.2选择排序 5 3.3交换排序 6 3.4冒泡排序 8 3.5希尔排序 9 3.6归并排序 11 4调试与测试13 4.1程序模块图 13 4.2程序代码 13 4.3程序运行 22 课程设计总结 24  1 课题需求描述 1.1 课题来源 排序是数据处理中经常使用的一种重要运算。设文件由n个记录{R1,R2，??，Rn}组成，如n个学生记录，每个学生记录包括学号、姓名、班级等。n个记录对应的关键字集合为{K1,K2,??,Kn}，如学生的学号。所谓排序就是将这n个记录按关键字大小递增或递减重新排列。 当待排序记录的关键字均不相同时，排序结果是唯一的，否则排序结果不唯一。如果文件中关键字相同的记录经过某种排序方法进行排序后，仍能保持它们在排序之前的相对次序，则称这种排序方法是稳定的；否则，这种排序方法是不稳定的。 由于文件大小不同使排序过程中涉及的储存器不同，可将排序分成内部排序和外部排序两类。整个排序过程都在内存进行的排序，称为内部排序；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。内排序适用于记录个数不是很多的小文件，而外排序则适用于记录个数太多，不能一次性放入内存的大文件。 按策略划分，内部排序方法可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。 几乎所有的排序都有两个基本的操作： （1）关键字大小的比较。 （2）改变记录的位置。具体处理方式依赖于记录的存储形式，对于顺序型记录，一般移动记录本身，而链式存储的记录则通过改变指向记录的指针实现重定位。 排序算法很多，不同的算法有不同的优缺点，没有哪种算法在任何情况下都是最好的。评价一种排序算法好坏的标准主要有两条： （1）执行时间和所需的辅助空间，即时间复杂度和空间复杂度； （2）算法本身的复杂程度，比如算法是否易读、是否易于实现。 2 总体设计 2.1总体方案 （1）插入排序：每次将一个待排序的记录，按其关键字大小插入到前面已经排好 序的记录集中，使记录依然有序，直到所有待排序记录全部插入完成。 （2）选择排序：每一趟从待排序的数据中选出最小元素，顺序放在已排好序的数 据最后，直到全部数据排序完毕。 （3）交换排序：两两比较待排序的数据，发现两个数据的次序相反则进行交换， 直到没有反序的数据为止。 （4）归并排序：归并排序是利用“归并”技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。实现方法有两种：自底向上和自底向下。 自底向上的基本思想是：第1趟归并排序时，将数列A[1..n]看作是n个长度为1的有序序列，将这些序列两两归并，若n为偶数，则得到[n/2]个长度为2的有序序列；若n为奇数，则最后一个子序列不参与归并。第2趟归并则是将第一趟归并所得到的有序序列两两归并。如此反复，直到最后得到一个长度为n的有序文件为止。 自顶向下的基本方法：分治法。其三个步骤： 1.分解：将当前区间一分为二； 2.求解：递归地对两个子区间进行归并排序； 3.组合：将已排序的子区间归并为一个有序区间（终结条件：子区间长度为1） （5）冒泡 最多进行n-1趟排序，每趟排序时，从底部向上扫描，一旦发现两个相邻的元素不符合规则，则交换。我们发现，第一趟排序后，最小值在A[1]，第二趟排序后，较小值在A[2]，第n-1趟排序完成后，所有元素完全按顺序排列。 （6）希尔排序 任取一个小于n的整数1作为增量，把分