数据结构课程设计排序算法比较

《数据结构课程设计排序算法比较》由会员分享，可在线阅读，更多相关《数据结构课程设计排序算法比较（15页珍藏版）》请在装配图网上搜索。

1、课程设计报告数据结构课程设计题目：各种排序 学生姓名：高扬专 业：网络工程班 级：10211302学 号：1021130221指导教师：姜林 王志波2012年6 月27 日目 录排序算法比较一、 程序要求分析二、 程序主要功能三、 程序运行平台四、 程序数据结构五、 算法及时间复杂度六、 程序源代码七、自我总结各 种 排 序一、需求分析任务：用程序实现插入法排序、起泡法、选择法、快速法、合并法排序；输入的数据形式为任何一个正整数，大小不限。输出的形式：数字大小逐个递增的数列。要求给出多组不同元素个数的输入数据，并用列表打印出每种排序下的各趟排序结果。每个排序法结束时应打印出其元素比较的次数和交

2、换的次数。此程序需将结果用列表打印，一定要将其打印结果排列好。二、程序的主要功能1.用户输入任意个数，产生相应数量的随机数2.用户可以自己选择排序方式（直接插入排序，冒泡排序、快速排序、选择排序、二路归并排序五种排序方法）的一种3.程序给出原始数据、排序后从小到大的数据，并给出排序所用的时间，比较的总次数和交换的总次数。三、程序运行平台Visual C+ 6.0版本四、数据结构1.类： NuovSortpublic:void Myface();void choose();void insertsort(int R,int n); /直接插入排序法void Bubblesort(int R,in

3、t n); /冒泡排序算法实现void quicksort(int R,int left,int right); /快速排序算法实现void selectsort(int R,int n); /直接选择排序算法实现void merge(int R,int A,int s,int m,int t);/二路归并排序算法实现void mergepass(int R,int A,int n,int c);void mergesort(int R,int n);2.主界面：Myface() /界面cout各种排序算法实现-endl; cout#endl; cout# 1.直接插入排序 #endl; co

4、ut# 2.冒泡排序 #endl; cout# 3.快速排序 #endl; cout# 4.直接选择排序 #endl; cout# 5.二路归并排序 #endl; cout#endl; coutenter your choose:;3.选择界面：choose()int i,x,n,s,t;time_t t1,t2;double tt1,tt2,tt3,tt4,tt5;coutttt 欢迎您使用 高扬 的排序程序endl;cout请问，需要几个被排序数字？endl;docoutn;while(n500);int left=0,right=n-1; for(i=0;in;i+) Ri=rand()

5、%888+1; /产生随机数 cout被排序的数字随机产生如下：endl; for(i=0;in;i+) coutRi ; coutendl; coutm; switch(m) case 1:t1=time(NULL);insertsort(R,n);t2=time(NULL);tt1=difftime(t2,t1); cout排序所需时间为：tt1endl;break; /直接插入排序算法实现 case 2:t1=time(NULL);Bubblesort(R,n);t2=time(NULL);tt2=difftime(t2,t1); cout排序所需时间为：tt2endl;break; /

6、冒泡排序算法实现 case 3:t1=time(NULL); coutBefore the sort,your answer is:; for(x=0;xn;x+) cout.width(4); coutRx ; coutendl; quicksort(R,left,right); cout排序的结果是：; for(x=0;xn;x+) coutRx ; coutendl; coutendl; cout元素比较次数为comN3次endl; cout元素交换次数为chaN3次endl; t2=time(NULL);tt3=difftime(t2,t1); cout排序所需时间为：tt3endl;

7、break; /快速排序算法实现 case 4:t1=time(NULL);selectsort(R,n);t2=time(NULL);tt4=difftime(t2,t1); cout排序所需时间为：tt4endl;break; /直接选择排序算法实现 case 5:t1=time(NULL);mergesort(R,n); coutendl; cout元素比较次数为comN5次endl; cout元素交换次数为chaN5次endl;t2=time(NULL);tt5=difftime(t2,t1); cout排序所需时间为：tt5endl;break; /二路归并排序算法实现 defaul

8、t:coutinput error !endl;choose(); 五、算法及时间复杂度（一）各个排序的算法思想：（1）直接插入排序算法思想：将一个记录插入到已排好的有序表中，从而得到一个新的，记录数增加1的有序表。（2）起泡排序算法思想：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直到第N-1和第N个记录的关键字进行过比较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序，对前N-1个记录进行同样操作。一共要进行N-1趟起泡排序。（3）快速排序算法思想：

9、通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。（4）选择排序算法思想：通过N-I次关键字间的比较，从N-I+1个记录中选出关键字最小的记录，并和第I（1=I=N）个记录交换。（5）二路归并排序算法思想：先将每个数确定为一个空间，然后两两比较，把排序后的结果放在新数组中，然后再两两比较，以此类推，最终把所有的子区间合并为一个区间。（二）时间复杂度分析排序算法 最差时间时间复杂度 是否稳定？冒泡排序O(n2)O(n2) 稳定 快速排序O(n2)O(n*log2n) 不稳定 选择排序O(n2)O(n

10、2) 稳定 六、程序源代码/*设计要求：利用随机函数产生N个随机整数（N = 1到500），利用直接插入排序，冒泡排序、快速排序、选择排序、二路归并排序五种排序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间，比较的总次数和交换的总次数。#include#include#include#include#includeusing namespace std;const int maxsize=500;int Rmaxsize;int Amaxsize;int i,n,right,left;int comN1=0,chaN1=0; /直接插入排序中元素比较的

11、次数和交换的次数int comN2=0,chaN2=0; /冒泡排序中元素比较的次数和交换的次数int comN3=0,chaN3=0; /快速排序中元素比较的次数和交换的次数int comN4=0,chaN4=0; /直接选择排序中元素比较的次数和交换的次数int comN5=0,chaN5=0; /合并排序中元素比较的次数和交换的次数class NuovSortpublic:void Myface();void choose();void insertsort(int R,int n); /直接插入排序法void Bubblesort(int R,int n); /冒泡排序算法实现void

12、 quicksort(int R,int left,int right); /快速排序算法实现void selectsort(int R,int n); /直接选择排序算法实现void merge(int R,int A,int s,int m,int t);/二路归并排序算法实现void mergepass(int R,int A,int n,int c);void mergesort(int R,int n);void NuovSort:Myface() /界面cout各种排序算法实现-endl; cout#endl; cout# 1.直接插入排序 #endl; cout# 2.冒泡排序

13、#endl; cout# 3.快速排序 #endl; cout# 4.直接选择排序 #endl; cout# 5.二路归并排序 #endl; cout#endl; coutenter your choose:;void Display(int R, int n)for(int i=0;in;i+)cout.width(4);coutRi;coutendlendl;void NuovSort:choose()int i,x,n,s,t;time_t t1,t2;double tt1,tt2,tt3,tt4,tt5;coutttt 欢迎您使用 高扬 的排序程序endl;cout请问，需要几个被排序

14、数字？endl;docoutn;while(n500);int left=0,right=n-1; for(i=0;in;i+) Ri=rand()%888+1; /产生随机数 cout被排序的数字随机产生如下：endl; for(i=0;in;i+) coutRi ; coutendl; coutm; switch(m) case 1:t1=time(NULL);insertsort(R,n);t2=time(NULL);tt1=difftime(t2,t1); cout排序所需时间为：tt1endl;break; /直接插入排序算法实现 case 2:t1=time(NULL);Bubbl

15、esort(R,n);t2=time(NULL);tt2=difftime(t2,t1); cout排序所需时间为：tt2endl;break; /冒泡排序算法实现 case 3:t1=time(NULL); coutBefore the sort,your answer is:; for(x=0;xn;x+) cout.width(4); coutRx ; coutendl; quicksort(R,left,right); cout排序的结果是：; for(x=0;xn;x+) coutRx ; coutendl; coutendl; cout元素比较次数为comN3次endl; cout

16、元素交换次数为chaN3次endl; t2=time(NULL);tt3=difftime(t2,t1); cout排序所需时间为：tt3endl;break; /快速排序算法实现 case 4:t1=time(NULL);selectsort(R,n);t2=time(NULL);tt4=difftime(t2,t1); cout排序所需时间为：tt4endl;break; /直接选择排序算法实现 case 5:t1=time(NULL);mergesort(R,n); coutendl; cout元素比较次数为comN5次endl; cout元素交换次数为chaN5次endl;t2=tim

17、e(NULL);tt5=difftime(t2,t1); cout排序所需时间为：tt5endl;break; /二路归并排序算法实现 default:coutinput error !endl;choose(); /直接插入排序算法实现void NuovSort:insertsort(int R,int n)int p,x=1;for(int i=1;i=0)&(tempRj)comN1+;Rj+1=Rj;j-;comN1+;Rj+1=temp;chaN1+;cout第x+趟被排序的数字如下：endl;for(p=0;pn;p+)cout.width(4);coutRp ;coutendl;

18、coutendl;cout元素比较次数为comN1次endl;cout元素交换次数为chaN1次endl;/冒泡排序算法实现void NuovSort:Bubblesort(int R,int n)int flag=1;int x=1; /当flag为0时则停止排序for(int i=1;in;i+)for(int i=1;i=i;j-)comN2+;if(RjRj-1)/发生逆序int t=Rj;Rj=Rj-1;Rj-1=t;flag=1;/交换，并标记发生了变化chaN2+;cout第x+趟被排序的数字如下：endl;for(i=0;in;i+)cout.width(4);coutRi;c

19、outendl;if(flag=0)break;coutendl;cout元素比较次数为comN2次endl;cout元素交换次数为chaN2次endl;/快速排序算法实现void NuovSort:quicksort(int R,int left,int right)int k=left,j=right;int n=right;int t,temp=Rk;while(ktemp)&(jk)comN3+;j-;if(kj)t=Rk;Rk=Rj;Rj=t;chaN3+;k+;while(Rktemp)&(kj)comN3+;k+;if(kj)t=Rk;Rk=Rj;Rj=t;chaN3+;j-;/

20、一次划分得到基准值的正确位置Rk=temp;if(leftk-1)quicksort(R,left,k-1);if(k+1right)quicksort(R,k+1,right);/直接选择排序算法实现void NuovSort:selectsort(int R,int n)int i,j,m,p;int t;for(i=0;in-1;i+)m=i;for(j=i+1;jn;j+)if(RjRm)comN4+;m=j;if(m!=i)t=Ri;Ri=Rm;Rm=t;chaN4+;cout第i+1趟被排序的数字如下：endl;for(p=0;pn;p+)cout.width(4);coutRp

21、;coutendl;coutendl;cout元素比较次数为comN4次endl;cout元素交换次数为chaN4次endl;/二路归并排序算法实现void NuovSort:merge(int R,int A,int s,int m,int t)/将两个子区间RsRm和Rm+1Rt合并，结果存储在A中int i,j,temp;i=s;j=m+1;while(i=m)&(j=Rj)chaN5+;temp=Rj;for(int k=j-1;k=i;k-)Rk+1=Rk;Ri=temp;j+;elsei+;for(int l=s;l=t;l+)Al=Rl;void NuovSort:mergepa

22、ss(int R,int A,int n,int c)/对R数组做一趟排序归并，结果存入A数组中，n为元素个数，c为区间长度int i,j;i=0;while(i+2*c-1=n-1)/长度均为c的两个区间合并成一个区间merge(R,A,i,i+c-1,i+2*c-1);i+=2*c;if(i+c-1n) /长度不等的两个区间合并成一个区间merge(R,A,i,i+c-1,n-1);else /仅剩一个区间时直接复制到A中for(j=i;j=n-1;j+)Aj=Rj;void NuovSort:mergesort(int R,int n)int c=1,i=0,k=1;int Amaxsi

23、ze;cout二路归并排序的每一次的结果如下：endlendl;cout初始状态:;Display(R,n);while(cn)mergepass(R,A,n,c); /一次合并且结果存入A中i=i+1; cout第k趟: ;k+; Display(R,n);c*=2;mergepass(A,R,n,c); /再次合并且结果存入R中i=i+1; cout第k趟: ;k+; Display(R,n);c*=2;/函数的实现int main()NuovSort v;char ch;cout各种排序算法实现-endl;dov.choose();coutendl;cout 继续操作按Y;,退出按N -

24、ch;while(ch!=Y&ch!=N)cout请根据提示操作！# 继续操作按Y;,退出按N #ch;while(ch!=N); return 0;七、自我总结 经过三天的努力，终于做完了这份程序。我发现，做任何事情决定都应该有个总体规划，每天做多少，做到什么程度，之后的工作按照规划逐步展开完成。对于一个完整的程序设计，首先需要总体规划写程序的步骤，分块写分函数写，然后写完一部分马上纠错调试。1、 感觉一开始设计结构写函数体现的是数据结构的思想，后面的调试则更加体现了人的综合素质，专业知识、坚定耐心、锲而不舍，真的缺一不可啊。2、 通过这次课设，不仅仅复习了C语言相关知识、巩固了数据结构关于排序的算法等知识，更磨练了我的意志。3、 做的过程中，老师教会了我如何调试错误，即每一步应该出现什么情况都应该用类似于cout 这样的方法做输出，这样才能知道具体的每一步的情况是否和预想的一样，也方便与自己找出问题的原因。4、 快速排序的代码是自己根据思想写出来的，因为参考的地方有错，所以选择自己写，不过通过自己努力，让结果实现了，从中明白，只要努力，就会成功。