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

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

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

3、esort(int r,int 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.直接

4、插入排序 #endl; cout# 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

5、;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);bubblesort(r,n);t2=time(null);tt2=difftime(t2,t1); cout排序所需时间为：tt

6、2endl;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元素交换次数为chan3次endl; t2=time(null);tt3=difftime(t2,t1); cout排序

7、所需时间为：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=time(null);tt5=difftime(t2,t1); cout排序所需时间为：tt5endl;break; /二路归

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

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

10、定 选择排序o(n2)o(n2) 稳定 六、程序源代码/*设计要求：利用随机函数产生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);

12、 /冒泡排序算法实现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);void nuovsort:myface() /界面cout各种排序算法实现-endl; cout#endl; cout# 1.直接插入排序 #endl;

13、 cout# 2.冒泡排序 #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;

14、cout请问，需要几个被排序数字？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=ti

15、me(null);bubblesort(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元素比较次数为co

16、mn3次endl; cout元素交换次数为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元素交换次数为cha

17、n5次endl;t2=time(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);cou

18、trp ;coutendl;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.wid

19、th(4);coutri;coutendl;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

20、=t;chan3+;j-;/一次划分得到基准值的正确位置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.wi

21、dth(4);coutrp ;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 nu

22、ovsort:mergepass(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 amaxsize;cout二路归并排序的每一次的结果如下：endlendl;cout初始状态:;display(r,n);