《数据排序C程序设计课程设计报告》由会员分享，可在线阅读，更多相关《数据排序C程序设计课程设计报告（24页珍藏版）》请在金锄头文库上搜索。
1、淮阴工学院C+程序设计课程设计报告选题名称：数据排序系（院）：专 业:班 级:姓 名:学号:指导教师:学年学期:20152016 学年第 2 学期2016 年 6 月 28 日摘要：排序是数据处理中经常使用的一种重要运算。设文件由 n个记录Ri, R2, Rn 组成，如 n 个学生记录，每个学生记录包括学号、姓名、班级等。 n 个记录对应的 关键字集合为Ki, K2,Kn，如学生的学号。所谓排序就是将这 n个记录按关 键字大小递增或递减重新排列。当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。 如果文件中关键字相同的记录经过某种排序方法进行排序之后，仍能保持它们在排序 之
2、前的相对次序，则称这种排序方法是稳定的；否则，称这种排序方法是不稳定的。由于文件大小不同使排序过程中涉及的存储器不同，可将排序分成内部排序和外 部排序两类。整个排序过程都在内存进行的排序，称为内部排序；这里，主要讨论内 部排序，外部排序不考虑。内部排序方法可以分为五类：插入排序、选择排序、交换排序、归并排序和分配 排序。几乎所有的排序都有两个基本的操作：(1) 关键字大小的比较。(2) 改变记录的位置。具体处理方式依赖于记录的存储形式，对于顺序型记录， 一般移动记录本身，而链式存储的记录则通过改变指向记录的指针实现重定位。 关键词： 插入排序；选择排序；冒泡排序；归并排序；希尔排序；交换排序#
3、 / 243 / 24目录1 课题需求描述 01.1 课题来源 02 总体设计 12.1总体方案 13 详细设计和实现 23.1插入排序 23.2选择排序 33.3 交换排序 43.4冒泡排序 53.5希尔排序 63.6归并排序 84 调试和测试 94.1 程序模块图 94.2 程序代码 104.3 程序运行 17课程设计总结 错误 !未定义书签。1 课题需求描述1.1 课题来源排序是数据处理中经常使用的一种重要运算。设文件由n个记录R1,R2 , , , Rn组成，如 n 个学生记录，每个学生记录包括学号、姓名、班级等。n 个记录对应的关键字集合为K1,K2, , ,Kn，如学生的学号。所谓
4、排序就是将这 n个记录按关键字大小递 增或递减重新排列。当待排序记录的关键字均不相同时，排序结果是唯一的，否则排序结果不唯一。 如果文件中关键字相同的记录经过某种排序方法进行排序后，仍能保持它们在排序之 前的相对次序，则称这种排序方法是稳定的；否则，这种排序方法是不稳定的。由于文件大小不同使排序过程中涉及的储存器不同，可将排序分成内部排序和外 部排序两类。整个排序过程都在内存进行的排序，称为内部排序；反之，若排序过程 中要进行数据的内、外存交换，则称之为外部排序。内排序适用于记录个数不是很多 的小文件，而外排序则适用于记录个数太多，不能一次性放入内存的大文件。按策略划分，内部排序方法可以分为五
5、类：插入排序、选择排序、交换排序、归 并排序和分配排序。几乎所有的排序都有两个基本的操作：（1）关键字大小的比较。（2）改变记录的位置。具体处理方式依赖于记录的存储形式，对于顺序型记录， 一般移动记录本身，而链式存储的记录则通过改变指向记录的指针实现重定位。排序算法很多，不同的算法有不同的优缺点，没有哪种算法在任何情况下都是 最好的。评价一种排序算法好坏的标准主要有两条：（1）执行时间和所需的辅助空间，即时间复杂度和空间复杂度；（2）算法本身的复杂程度，比如算法是否易读、是否易于实现。2 总体设计2.1 总体方案（1）插入排序：每次将一个待排序的记录，按其关键字大小插入到前面已经排好 序的记录
6、集中，使记录依然有序，直到所有待排序记录全部插入完成。（2）选择排序：每一趟从待排序的数据中选出最小元素，顺序放在已排好序的数 据最后，直到全部数据排序完毕。（3）交换排序：两两比较待排序的数据，发现两个数据的次序相反则进行交换， 直到没有反序的数据为止。（4）归并排序：归并排序是利用“归并”技术来进行排序。归并是指将若干个已 排序的子文件合并成一个有序的文件。实现方法有两种：自底向上和自底向下。自底向上的基本思想是：第1趟归并排序时，将数列A1.n看作是n个长 度为1的有序序列，将这些序列两两归并，若 n为偶数，则得到n/2个长度为2的有 序序列；若 n 为奇数，则最后一个子序列不参和归并。
7、第 2 趟归并则是将第一趟归并 所得到的有序序列两两归并。如此反复，直到最后得到一个长度为 n 的有序文件为止。自顶向下的基本方法：分治法。其三个步骤：1. 分解：将当前区间一分为二；2. 求解：递归地对两个子区间进行归并排序；3. 组合：将已排序的子区间归并为一个有序区间 （终结条件： 子区间长度为 1）（5）冒泡最多进行 n-1 趟排序，每趟排序时，从底部向上扫描，一旦发现两个相邻的元素 不符合规则，则交换。我们发现，第一趟排序后，最小值在 A1 ，第二趟排序后，较 小值在 A2 ，第 n-1 趟排序完成后，所有元素完全按顺序排列。（6）希尔排序任取一个小于n的整数Si作为增量，把所有元素
8、分成 S个组。所有间距为S的元素放在同一个组中。第一组：A1， AS1+1，A2*Si+1，第二组：A2， AS1+2，A2*Si+2，第三组：A3， AS1+3，A2*Si+3，第 Si 组：ASi , A2*Si , A3*Si,先在各组内进行直接插人排序；然后，取第二个增量 S2 (S)重复上述的分组和 排序，直至所取的增量S=1(SS-ivS-2SS)，即所有记录放在同一组中进行直接 插入排序为止。3 详细设计和实现3.1 插入排序假设待排序数据存放在数组 A1. .n中，则A1可看作是一个有序序列，让i从2 开始，依次将Ai插入到有序序列A1.i-1中，An插入完毕则整个过程结束，A
9、1.n 成为有序序列。排序过程示例用【】表示有序序列)待排序数据： 【25】5485421 19727315( n=10 )i=22554】85421 19727315i=382554】5421 19727315i=482554 54】21 19727315i=582125 54 54】 19727315i=61821255454】9727315i=71821255454 97】27315i=8128212554 5497】7315i=9128212554 547397】15i=10 ：【128152125 545473 97】排序结束程序编写：int charu(int b,int c)/将
10、第一个看作有序数列，后面的数插入system(cls);int i,x,j;cout 初始值 :;print1(b,c);for(i=1;ic;i+)x=bi;j=i-1;while(x=0)bj+1=bj; j-;bj+1=x;# / 240 / 24cout排序后:;prin t1(b,c); return 1;3.2选择排序选择排序的基本思想是：每一趟从待排序的数据中选出最小元素，顺序放在已排好序的数据最后，直到全部数据排序完毕。过程模拟待排序数据92286284621656873366第一趟排序16286284629256873366第二趟排序16286284629256873366第
11、三趟排序16283384629256876266第四趟排序 :16283356629284876266第五趟排序16283356629284876266第六趟排序16283356626284879266第七趟排序 :16283356626266879284第八趟排序16283356626266849287第九趟排序16283356626266848792程序编写int xua nze(i nt b,i nt c)system(cls);int i,j,t,p; cout初始值:;prin t1(b,c); for(i=0;i=c-2;i+) p=i;for(j=i+1;jbj)P=j; if(
12、p!=i) t=bp; bp=bi; bi=t; cout排序后:;prin t1(b,c); return 1;3.3 交换排序交换排序的基本思想是：两两比较待排序的数据，发现两个数据的次序相反则进行交换，直到 没有反序的数据为止。排序思想在 A1.n 中任取一个数据元素作为比较的 “基准”(不妨记为 X )，将数据区划分为左右两个部 分：A1.i-1和 Ai+1.n，且 A1.i-1 X Ai+1.n(1 i n)，当 A1.i-1和 Ai+1.n非空时，分 别对它们进行上述的划分过程，直至所有数据元素均已排序为止。排序过程示例待排序数据：6767145229990548771X=67ij扫描 jij交换5467145229990678771扫描 iij交换5467145229967908771j=i ，结束ij第一趟排序后： 5467 1452299 67908771第二趟排序后： 929 14525467 67718790第三趟排序后： 929 14525467 6771 8790第四
