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

1、 数据结构与算法设计课程设计报告 题目： 排序算法比较 学生姓名： 汪洪 学 号： 201120181805 班 级： 1121822 指导教师： 周华清 2013年1月10日目录需求分析··································&#

2、183;·····3总体设计········································4详细设计··

3、3;·····································5类的设计············

4、;·······················5现实部分··························

5、··············8随机数赋值·································8结果输出·&

6、#183;·································8直接插入排序···············

7、················9冒泡排序·································&

8、#183;·10选择排序···································11快速排序···········&

9、#183;·······················13堆排序·························&#

10、183;···········15二路归并排序·······························18程序测试·····

11、···································21总结··············&#

12、183;·····························251 需求分析本程序主要为了实现对各排序算法的性能比较。主要包括对直接插入排序，冒泡排序，选择排序，快速排序，堆排序二路归并排序六种排序算法在时间复杂度上的性能比较。基于此目的需要设定一个顺序表来产生一组数据，本程序用了一个长度为30000的

13、long int型数组并用了以时间为随机种子产生了一组数组。用六个模块来实现各种排序功能并在各模块中完成计算排序所用的时间。并用一个数组保存各种排序所用的时间。为了比较各种排序的在时间上的优劣性将各个排序所用的时间进行比较并输出结果！2 总体设计Switch结构设定long数组开始 进行快速排序进行冒泡排序进行冒泡排序进行选择排序 二路归并排序堆排序冒泡排序直接插入排序快速排序选择排序 保存所需时间进行二路归并排序进行堆排序进行选择排序进行直接插入排序 结束对所有排序的时间进行从小到大的排序并输出结果获得所有排序所花费的时间（包括未switch结构中未被选中的排序）保存所需时间保存所需时间保存

14、所需时间保存所需时间保存所需时间 3 详细设计1. 类的设计本程序功能只是为了比较各种排序算法在时间上的优劣。所以可以用一个类来完成的有的操作，固本程序只需定义一个类。为实现本程序功能定义一个类其中包括了一个长度300000的数组。并且为了实现各种排序功能应当设计功能函数分别实现各种类型的排序和排序后的结果。以下对这个类进行详细说明。类名：sortrather数据成员：long int aN 其中N为一个全局常量其值为30000，该成员用来保存一个用于保存一组数据用于排序。Long int time6该数组用于保存各种排序所用的时间，以便对种种排序所用时间进行比较。成员函数：1. void p

15、ubction（）实现功能：本函数的的作用是给数据成员 aN进行随机赋值。实现算法：用系统时间作为随机种子。再将随机函数对90000的取余赋给。aN.2. print()实现功能：将aN的前30个元素输出。实现算法：将数组元素一个一个的输出。3.void insertsort()实现功能：以直接插入排序算法完成对数组a的直接插入排序。实现算法：以当前元素以基准元素，将后面的元素与其进行比较。如果比当前元素大则直接插到当前元素后面。否则把当前元素后移并置当前元素为前一个元素。重复此步骤。4void bubblesort()实现功能：以冒泡的方式对数组aN进行排序。实现算法：从第N-1个数开始与前

16、一个数比较使之小的在的前大的在后，直到第1个数，这样便找到了最小的用同样的方法找到第二小的数······。3. void selectsort(long int a,long int n)实现功能：以选择排序的方法完成对aN的排序。实现算法：依次取数组aN中的第一个、第二个······到第aN个，与数组中它所在位置后的其它元素进行比较并使a1,a2,.aN取余下元素的最小值。4. void quick(long int a,long int left,long int rig

17、ht)实现功能：用快递排序的方法来实现对aN从小到大的排序实现算法：先取a1作为基准点从a-1开始依次与基准点比较若a1大于其中的某个数则交换a1与这个数的值。并以该数为基准点从a2开始从复以上步骤真以基准点为界两边的数大小被分开。再对分好区间执行此步骤。5.void heapsort(long int a);实现功能：用堆排序对数组aN进行排序。实现算法：从N/2开始双数组进行移位使得对于数组中满足ai>a2*i,ai>a2*i+1.6. void mergesort(long int a);实现功能：用二路归并排序对数组aN进行排序。实现算法：先以N/2为间隔对数组aN进行直接

18、插入排序。依次使N=N/2缩小间隔。最终作一次直接插入排序。实现部分对数组随机赋值void pubction()srand(time(NULL);for(long int i=0;i<N;i+) ai=rand()%90000;输出数组前30个元素void print(long int a)int i;for(i=0;i<W;i+)cout<<ai<<"t"cout<<endl;直接插入排序void insertsort(long int a)long int i,j,temp;pubction(a);/cout<<

19、;"初始数组是：n" /print(a);for(i=1;i<N;i+)temp=ai;for(j=i-1;j>=0;j-)if(temp<aj)ppp0+;aj+1=aj;elsebreak;aj+1=temp;/cout<<"直接排序后的数组是：n"/print(a);cout<<"直接插入排序耗时： "<<ppp0/100000<<"毫秒"<<endl;冒泡排序void bubblesort(long int a)long int

20、i,j,temp;pubction(a);/cout<<"初始数组是：n"/print(a);for(i=0;i<N;i+)for(j=N-1;j>i;j-)if(aj<aj-1)ppp1+;temp=aj;aj=aj-1;aj-1=temp;/cout<<"冒泡排序后的数组是：n"/print(a);cout<<"冒泡排序耗时为： "<<ppp1/100000<<"毫秒"<<endl;选择排序void selectsort(

21、long int a,long int n)long int i,j,temp,k;char trtemp40,trt40;if(n>6)pubction(a);for(i=0;i<n-1;i+)temp=ai;for(j=i+1;j<n;j+)if(temp>aj)ppp2+;k=aj;aj=temp;temp=k;ai=temp;cout<<"选择排序耗时为： "<<ppp2/100000<<"毫秒"<<endl;elsefor(i=0;i<n-1;i+)temp=ai;s

22、trcpy(trtemp,sti);for(j=i+1;j<n;j+)if(temp>=aj)strcpy(trt,stj);strcpy(stj,trtemp);strcpy(trtemp,trt);k=aj;aj=temp;temp=k;strcpy(sti,trtemp);ai=temp;ai/=100000;ai/=100000;快速排序void quick(long int a,long int left,long int right)long int i=left,j=right,temp;temp=ai;if(j>i)while(j>i)while(aj&

23、gt;temp)&&(i<j)j-;if(i<j)ppp3+;ai=aj;i+;while(ai<temp)&&(i<j)i+;if(i<j)ppp3+;aj=ai;j-;ai=temp;quick(a,left,i-1);quick(a,i+1,right);void Quick(long int a)long int i=0,j=N-1;pubction(a);/cout<<"初始数组是：n"/print(a);quick(a,i,j);/cout<<"快速排序后数组是：n&

24、quot;/print(a);cout<<"快速排序耗时为： "<<ppp3/100000<<"毫秒"<<endl;堆排序void creatheap(long int a,long int i,long int n)long int j,temp;temp=ai;j=2*i+1;while(j<=n)if(j<=n)if(j+1<=n)if(aj<aj+1)j+;if(temp<aj)ppp4+;ai=aj;i=j;j=2*i+1;else j=n+1;ai=temp;voi

25、d heapsort(long int a)int temp,j;int n=N-1;pubction(a);/cout<<"初始数组为：n"/print(a);for(int i=n/2;i>=0;i-)creatheap(a,i,n);for(j=n;j>=1;j-)temp=a0;a0=aj;aj=temp;creatheap(a,0,j-1);/cout<<"堆排序后的数组是:n"/print(a);cout<<"堆排序耗时为： "<<ppp4/100000<&

26、lt;"毫秒"<<endl;二路归并排序void merge(long int a,long int c,long int l,long int m,long int n)long int i=l,j=m,k=l;if(ai>aj)ck=aj;j+;elseck=ai;i+;k+;while(i<m)&&(j<n)while(ai<aj)&&(i<m)&&(j<n)ppp5+;ck=ai;k+;i+;while(ai>=aj)&&(i<m)&&

27、amp;(j<n)ppp5+;ck=aj;k+;j+;if(i>=m)while(j<n)ppp5+;ck=aj;k+;j+;else if(j>=n)while(i<m)ppp5+;ck=ai;k+;i+;for(long int p=l;p<n;p+)ap=cp;void mergesort(long int a)long int cN,d=1,i=0;/cout<<"初始数组为：n"pubction(a);/print(a);for(d;d<N-1;d*=2)i=0;while(i<N)if(i+d>=N-1)merge(a,c,i,N,N);e