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

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

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

3、录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，如学生的学号。所谓排序就是将这 n个记录按

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

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

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

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

8、素放在同一个组中。第一组：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(S<S-ivS-2<<S<S)，即所有记录放在同一组中进行直接 插入排序为止。3 详细设计和实现3.1 插入排序假设待排序数据存放在数组 A1. .n中，则A1可看作是一个有序序列，让i从2 开始，依次将Ai插入到有序序列A1.i-1中，An插入完毕则整个过

9、程结束，A1.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

10、 c)/将第一个看作有序数列，后面的数插入system("cls");int i,x,j;cout<<" 初始值 :"print1(b,c);for(i=1;i<c;i+)x=bi;j=i-1;while(x<bj && j>=0)bj+1=bj; j-;bj+1=x;cout<<"排序后:"prin t1(b,c); return 1;3.2选择排序选择排序的基本思想是：每一趟从待排序的数据中选出最小元素，顺序放在已排好序的数据最后，直到全部数据排序完毕。过程模拟待排序数据9

11、2286284621656873366第一趟排序16286284629256873366第二趟排序16286284629256873366第三趟排序16283384629256876266第四趟排序 :16283356629284876266第五趟排序16283356629284876266第六趟排序16283356626284879266第七趟排序 :16283356626266879284第八趟排序16283356626266849287第九趟排序16283356626266848792程序编写int xua nze(i nt b,i nt c)system("cls"

12、);int i,j,t,p; cout<<"初始值:"prin t1(b,c); for(i=0;i<=c-2;i+) p=i;for(j=i+1;j<=c-1;j+) if(bp>bj)P=j; if(p!=i) t=bp; bp=bi; bi=t; cout<<"排序后:"prin t1(b,c); return 1;3.3 交换排序交换排序的基本思想是：两两比较待排序的数据，发现两个数据的次序相反则进行交换，直到 没有反序的数据为止。排序思想在 A1.n 中任取一个数据元素作为比较的 “基准”(不妨记为 X

13、 )，将数据区划分为左右两个部 分：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 145

14、25467 6771 8790第四趟排序后： 914 29 525467 67718790第五趟排序后： 914 29525467 67 7187 90程序编写void swap(int *a, int *b)int temp = *a;*a = *b;*b = temp;int partition(int a, int low, int high)int privotKey = alow;/基准元素while(low < high)/从表的两端交替地向中间扫描while(low < high && ahigh >= privotKey)-high;/ 从 h

15、igh 所指位置向前搜索，至多到 low+1 位置。将比基准元素小的交换到低端swap(&alow, &ahigh);while(low < high && alow <= privotKey )+low;swap(&alow, &ahigh);return low;void qsort_improve(i nt r ,i nt low,i nt high, int k) if( high -low > k ) /int pivot = partiti on( r, low, high); / qsort_improve(r,

16、low, pivot - 1,k); qsort_improve(r, pivot + 1, high,k);void kuaisupaixu(i nt r, int n, int k)长度大于k时递归，k为指定的数调用的Partition 算法保持不变system("cls"); cout<<"初始值:II.prin t1(r, n+1); qsort_improve(r,0, n,k); for(i nt i=1; i<=n;i +)/int tmp = ri;int j=i-1;while(tmp < rj) rj+1=rj;j=j-

17、1;先调用改进算法Qsort使之基本有序再用插入排序对基本有序序列排序rj+1 = tmp;cout<<"排序后：" prin t1(r, n+1);3.4冒泡排序排序思想最多进行n-1趟排序，每趟排序时，从底部向上扫描，一旦发现两个相邻的元素不符合规则，则交换。我们发现，第一趟排序后，最小值在A1，第二趟排序后，较小值在A2，第n-1趟排序完成后，所有兀素完全按顺序排列。排序示例82201939待排序数据：533319533 63第一趟排序：寿3533319531963822039第二趟排序：3195333195320638239第三趟排序：319195333

18、2053396382第四趟排序：3 191920533339 536382第五趟排序：没有反序数据，排序结束程序编写int maopao(i nt b,i nt c)system("cls");cout<<"初始值："；prin t1(b,c);int i,j,t;for(i=0;i<c-1;i+)for(j=c-2;j>=i;j-)if(bj+1<bj)t=bj+1;bj+1=bj;bj=t;cout<<"排序后:"prin t1(b,c);return 1;3.5希尔排序基本思想S1个组。

19、所有间距为S1的元素放在同一任取一个小于n的整数3作为增量，把所有元素分成 个组中。第一组:A1 , AS 1+1 , A2*S 1+1,第二组：A2 , AS 1+2 , A2*S 1+2,第三组：A3 , AS 1+3 , A2*S 1+3,第 & 组：AS 1 , A2*S 1, A3*S 1,先在各组内进行直接插人排序；然后，取第二个增量S2 ( <S1 )重复上述的分组和排序，直至所取的增量St=1 (St<St-1<St-2< <S2<S1),即所有记录放在同一组中进行直接插入排序为止。排序示例序号12345678910原始数据12895

20、73296375457957S1=5组别排序结果1254532573789577996S2=3组别1排序结果1254532573789577996S-2组别排序结果 V5321237575479578996S4=1组别排序结果5123237545757798996编写程序void xiercharpaixu(i nt a, int n, int dk)for(i nt i= dk; i<n; +i)if(ai < ai-dk)/若第i个元素大于i-1元素，直接插入。小于的话,移动有序表后插入int j = i-dk;int x = ai;/复制为哨兵，即存储待排序元素ai = ai

21、-dk;/首先后移一个元素while(x < aj)查找在有序表的插入位置aj+dk = aj;j -= dk;/元素后移aj+dk = x;/插入到正确位置void xierpaixu(i nt a, int n)system("cls");cout«"初始值:"；prin t1(a, n);int dk = n/2;while( dk >= 1)xiercharpaixu(a, n, dk);dk = dk/2;coutvv"排序后:"；print1(a,n);3.6 归并排序归并排序有两种实现方法：自底向上

22、和自顶向下。自底向上的方法自底向上的基本思想是：第 1 趟归并排序时，将数列 A1.n 看作是 n 个长度为 1 的有序序列， 将这些序列两两归并，若 n为偶数，则得到n/2个长度为2的有序序列；若n为奇数，则最后一个 子序列不参和归并。第 2 趟归并则是将第 1 趟归并所得到的有序序列两两归并。如此反复，直到最 后得到一个长度为 n 的有序文件为止。上述的每次归并操作，均是将两个有序序列合并成一个有序序列，故称其为 “二路归并排序”类似地有 k(k>2) 路归并排序。自顶向下的方法 采用分治法进行自顶向下的算法设计，形式更为简洁。分治法的三个步骤： 设归并排序的当前区间是 Al.h ，

23、分治法的三个步骤是： 分解：将当前区间一分为二，即求分裂点 m=(l+h)/2 求解：递归地对两个子区间 Al.m 和 Am+1.h 进行归并排序； 组合：将已排序的两个子区间 Al.m 和 Am+1.h 归并为一个有序的区间 Al.h 。 递归的终结条件：子区间长度为1(一个数据组成的区间必然有序) 。void merge1(int *a,int left,int mid,int right)int*t=new intright-left+1；int m=left,n=mid+1,k=0； while(m<=mid)&&(n<=right)if(am<an)

24、tk+=am+；elsetk+=an+；while(m<=mid)tk+=am+；while(n<=right) tk+=an+； for(m=0,k=left；k<=right；)ak+=tm+；void sort(int *a,int left,int right)if(left<right)int m=(left+right)/2;sort(a,left,m);sort(a,m+1,right);merge1(a,left,m,right);int guib in (i nt r,i nt c)system("cls");cout<<

25、;"初始值："；prin t1(r,c);/ 数组r1的大小一定要不小于 rsort(r,0,c-1);cout<<"排序后："prin t1(r,c);return 1;4调试和测试4.1程序模块图Int main主函数完成输出的主界面以及输入数据的 方式Prin t1()完成输出菜单的功能int charu完成插入排序的功能Int xua nze完成选择排序的功能Int maopao完成冒泡排序的功能void merge1 void sortint guib in二个程序共同完成归并排序void xiercharpaixuvoid xie

26、rpaixu两个程序共同完成希尔排序void xua nzepaixu完成二元排序void swapint partition void qsort_improvevoid kuaisupaixu四个程序完成交换排序4.2 程序代码#include<iostream.h>#include<iomanip.h> #include<stdlib.h> #include<time.h> #define N 10000 void print1(int b,int c) for(int i=0;i<c;i+) cout<<bi<&l

27、t;" "cout<<endl; /插入排序 int charu(int b,int c)/ 将第一个看作有序数列，后面的数插入 system("cls"); int i,x,j;cout<<" 初始值 :" print1(b,c);for(i=1;i<c;i+) x=bi;j=i-1; while(x<bj && j>=0) bj+1=bj; j-; bj+1=x; cout<<" 排序后 :"print1(b,c); return 1; /选

28、择排序 int xuanze(int b,int c) system("cls"); int i,j,t,p; cout<<" 初始值 :" print1(b,c);for(i=0;i<=c-2;i+) p=i;for(j=i+1;j<=c-1;j+)if(bp>bj)p=j;if(p!=i)t=bp; bp=bi; bi=t;cout<<" 排序后 :"print1(b,c);return 1;/冒泡int maopao(int b,int c)system("cls")

29、;cout<<" 初始值 :"print1(b,c);int i,j,t;for(i=0;i<c-1;i+)for(j=c-2;j>=i;j-) if(bj+1<bj) t=bj+1;bj+1=bj;bj=t;cout<<" 排序后 :"print1(b,c);return 1;/归并排序void merge1(int *a,int left,int mid,int right)int*t=new intright-left+1; int m=left,n=mid+1,k=0; while(m<=mid)&

30、amp;&(n<=right)if(am<an) tk+=am+;else tk+=an+;while(m<=mid) tk+=am+;while(n<=right) tk+=an+;for(m=0,k=left;k<=right;) ak+=tm+;void sort(int *a,int left,int right)if(left<right)int m=(left+right)/2; sort(a,left,m); sort(a,m+1,right); merge1(a,left,m,right);int guibin(int r,int c

31、) system("cls"); cout<<" 初始值 :" print1(r,c);/数组 r1 的大小一定要不小于 r sort(r,0,c-1); cout<<" 排序后： " print1(r,c);return 1;/希尔排序void xiercharpaixu(int a, int n, int dk)for(int i= dk; i<n; +i)if(ai < ai-dk)/ 若第 i 个元素大于 i-1 元素，直接插入。小于的话，移动有序表后插入int j = i-dk;int x

32、 = ai;/复制为哨兵，即存储待排序元素ai = ai-dk;/首先后移一个元素while(x < aj) / 查找在有序表的插入位置 aj+dk = aj; j -= dk;/ 元素后移aj+dk = x;/插入到正确位置void xierpaixu(int a, int n) system("cls"); cout<<" 初始值 :" print1(a,n); int dk = n/2; while( dk >= 1 ) xiercharpaixu(a, n, dk); dk = dk/2;cout<<"

33、; 排序后 :"print1(a,n);/交换排序void swap(int *a, int *b)int temp = *a;*a = *b;*b = temp;int partition(int a, int low, int high)int privotKey = alow;/ 基准元素while(low < high)/ 从表的两端交替地向中间扫描while(low < high && ahigh >= privotKey)-high; /从 high 所指位置向前搜索，至多到 low+1 位置。将比基准元素小的交换到 低端swap(&am

34、p;alow, &ahigh);while(low < high && alow <= privotKey )+low;swap(&alow, &ahigh);return low;void qsort_improve(int r ,int low,int high, int k)if( high -low > k ) /长度大于k时递归，k为指定的数int pivot = partition(r， low， high); / 调用的 Partition 算法保持不变qsort_improve(r, low, pivot - 1,k);

35、 qsort_improve(r, pivot + 1, high,k);void kuaisupaixu(int r, int n, int k)system("cls");cout<<" 初始值： "print1(r,n+1); qsort_improve(r,0,n,k);/ 先调用改进算法 Qsort 使之基本有序 for(int i=1; i<=n;i +)/ 再用插入排序对基本有序序列排序 int tmp = ri;int j=i-1; while(tmp < rj) rj+1=rj; j=j-1;rj+1 = tmp

36、;cout<<" 排序后 :" print1(r,n+1);/主程序段 int main()int aN;int s,p;char j,c,t,i;while(1)if(p)/ 切回主界面k: system("cls");cout<<setw(8)<<setfill(' ')<<" 手工输入请按 1(个数 <10)"<<endl; cout<<setw(8)<<setfill(' ')<<"

37、随机产生请按 0(个数 <10000)"<<endl; cout<<" 请输入 :"cin>>c;do if(c='0'|c='1')break;elsecout<<" 输入格式错误，请重新输入 :" cin>>c;while(1);if(c='1')system("cls");cout<<" 您选择手工输入！确认 (1),返回 (0):" cin>>t;doif(t=

38、'0'|t='1') break;elsecout<<" 输入格式错误，请重新输入 :" cin>>t;while(1);if(t='0')goto k;system("cls");cout<<" 请输入手工输入个数 :" cin>>s;cout<<" 请输入需排序的数据： "for(int k=0;k<s;k+) cin>>ak;elsesystem("cls");co

39、ut<<" 您选择随机输入！确认 (1),返回 (0):" cin>>t;doif(t='0'|t='1') break;elsecout<<" 输入格式错误，请重新输入 :" cin>>t;15 / 2415 / 24while(1);if(t='0')goto k;system("cls");cout<<" 请输入随机产生个数 cin>>s;srand(unsigned)time(NULL);for(i

40、nt k=0;k<s;k+)ak=rand()%900+100;插入排序 "<<endl; 选择排序 "<<endl; 冒泡排序 "<<endl;system("cls");/ 清屏函数 cout<<setw(27)<<setfill(' ')<<" 数据排序 "<<endl; cout<<setw(50)<<setfill('=')<<endl;cout<<

41、;setw(27)<<setfill(' ')<<"1.cout<<setw(27)<<setfill(' ')<<"2.cout<<setw(27)<<setfill(' ')<<"3.cout<<setw(27)<<setfill(' ')<<"4. 归并排序 "<<endl; cout<<setw(27)<<s

42、etfill(' ')<<"5. 希尔排序 "<<endl;cout<<setw(27)<<setfill(' ')<<"6. 交换排序 "<<endl; cout<<" "<<" 请选择( 16， 0：退出) :"<<endl;cout<<""<<endl;cout<<" 请输入 :" elsesys

43、tem("cls");cout<<" 谢谢使用！ "exit(0);cin>>j;doif(j='0'|j='1'|j='2'|j='3'|j='4'|j='5'|j='6'|j='7') break;elsecout<<" 输入格式错误，请重新输入 :" cin>>j;while(1);switch(j)case '1':charu(a,s);break;/ 插入排序case '2':