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

《数据排序---C--程序设计课程设计报告.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、淮阴工学院C++程序设计课程设计报告选题名称:数据排序系（院）:专业:班级:姓名:学号:指导教师:学年学期:2015~2016学年第2学期2016年6月28日摘要：排序是数据处理中经常使用的一种重要运算。设文件由n个记录{R1，R2，……，Rn}组成，如n个学生记录，每个学生记录包括学号、姓名、班级等。n个记录对应的关键字集合为{K1，K2，……，Kn}，如学生的学号。所谓排序就是将这n个记录按关键字大小递增或递减重新排列。当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。如果文件中关键字相同的记录经过某种排序方法进行排序之后，仍能保持它们在排序

2、之前的相对次序，则称这种排序方法是稳定的；否则，称这种排序方法是不稳定的。由于文件大小不同使排序过程中涉及的存储器不同，可将排序分成内部排序和外部排序两类。整个排序过程都在内存进行的排序，称为内部排序；这里，主要讨论内部排序，外部排序不考虑。内部排序方法可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。几乎所有的排序都有两个基本的操作：（1）关键字大小的比较。（2）改变记录的位置。具体处理方式依赖于记录的存储形式，对于顺序型记录，一般移动记录本身，而链式存储的记录则通过改变指向记录的指针实现重定位。关键词：插入排序；选择排序；冒泡排序；归并排序；希尔排

3、序；交换排序目录1课题需求描述11.1课题来源12总体设计22.1总体方案23详细设计与实现43.1插入排序43.2选择排序53.3交换排序63.4冒泡排序83.5希尔排序93.6归并排序114调试与测试134.1程序模块图134.2程序代码134.3程序运行22课程设计总结24《C++程序设计课程设计报告》1课题需求描述1.1课题来源排序是数据处理中经常使用的一种重要运算。设文件由n个记录{R1,R2，„„，Rn}组成，如n个学生记录，每个学生记录包括学号、姓名、班级等。n个记录对应的关键字集合为{K1,K2,„„,Kn}，如学生的学号。所谓排序就是将这n个记录按

4、关键字大小递增或递减重新排列。当待排序记录的关键字均不相同时，排序结果是唯一的，否则排序结果不唯一。如果文件中关键字相同的记录经过某种排序方法进行排序后，仍能保持它们在排序之前的相对次序，则称这种排序方法是稳定的；否则，这种排序方法是不稳定的。由于文件大小不同使排序过程中涉及的储存器不同，可将排序分成内部排序和外部排序两类。整个排序过程都在内存进行的排序，称为内部排序；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。内排序适用于记录个数不是很多的小文件，而外排序则适用于记录个数太多，不能一次性放入内存的大文件。按策略划分，内部排序方法可以分为五类：插入

5、排序、选择排序、交换排序、归并排序和分配排序。几乎所有的排序都有两个基本的操作：（1）关键字大小的比较。（2）改变记录的位置。具体处理方式依赖于记录的存储形式，对于顺序型记录，一般移动记录本身，而链式存储的记录则通过改变指向记录的指针实现重定位。排序算法很多，不同的算法有不同的优缺点，没有哪种算法在任何情况下都是最好的。评价一种排序算法好坏的标准主要有两条：（1）执行时间和所需的辅助空间，即时间复杂度和空间复杂度；（2）算法本身的复杂程度，比如算法是否易读、是否易于实现。0《C++程序设计课程设计报告》2总体设计2.1总体方案（1）插入排序：每次将一个待排序的记录，

6、按其关键字大小插入到前面已经排好序的记录集中，使记录依然有序，直到所有待排序记录全部插入完成。（2）选择排序：每一趟从待排序的数据中选出最小元素，顺序放在已排好序的数据最后，直到全部数据排序完毕。（3）交换排序：两两比较待排序的数据，发现两个数据的次序相反则进行交换，直到没有反序的数据为止。（4）归并排序：归并排序是利用“归并”技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。实现方法有两种：自底向上和自底向下。自底向上的基本思想是：第1趟归并排序时，将数列A[1..n]看作是n个长度为1的有序序列，将这些序列两两归并，若n为偶数，则得到[n/2]

7、个长度为2的有序序列；若n为奇数，则最后一个子序列不参与归并。第2趟归并则是将第一趟归并所得到的有序序列两两归并。如此反复，直到最后得到一个长度为n的有序文件为止。自顶向下的基本方法：分治法。其三个步骤：1.分解：将当前区间一分为二；2.求解：递归地对两个子区间进行归并排序；3.组合：将已排序的子区间归并为一个有序区间（终结条件：子区间长度为1）（5）冒泡最多进行n-1趟排序，每趟排序时，从底部向上扫描，一旦发现两个相邻的元素不符合规则，则交换。我们发现，第一趟排序后，最小值在A[1]，第二趟排序后，较小值在A[2]，第n-1趟排序完成后，所有元素完全按顺序排列