《算法分析与设计》排序问题的答案

1、题一 排序问题一、设计目掌握各种排序的基本思想。掌握各种排序方法的算法实现。掌握各种排序方法的优劣分析及花费的时间的计算。掌握各种排序方法所适应的不同场合二、设计内容和要求利用随机函数产生 3000 个随机整数，利用选择排序、起泡排序、快速排序、合并排序（归并排序）等排序方法进行排序，并统计每一种排序上机所花费的时间。参考答案一、题一（排序问题）二、运行环境（软、硬件环境编写程序：C 语言编译环境：VC+6.0软件：Windows764硬件：华硕PC 机三、算法设计的思想选择排序：每一趟，从待排序的数据元素中，选出最小的一个元素，按顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。最

2、终实现数据元素从小到大的排序。起泡排序：一次比较两个相邻的元素，如果第一个元素比第二个元素大，就将他们排序进行交换。通过不断对要排序的数列走访，依次比较相邻两个元素大小，从开始的第一对到结尾的最后一对。最终完成数据从小到大的排序。快速排序：通过一趟排序，将要排序的数据分成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小。再按上述方法对这两部分数据，分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。合并排序：将两个及两个以上有序表，合并成一个新的有序表。即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并在一起，形成整体有序序列。四、

3、算法的流程图选择排序待排序数据元素将数组第一个数设为键值待排序数据元素将数组第一个数设为键值扫描数组中最小的元素得到排序好的数组开始，令i=0开始，令i=0，j=i+1是xixj否temp=xi xi=xjxj=tempi=j否in是结束快速排序得到需合并的数组得到需合并的数组设数组第一个为键值得到后一个数存入大数组与键值比较存入小数组将小数组，键值，大数组连在原数组中大小数组分别递归合并排序开始，高位 high，低位 low，中点middleh为前段下标，j为后段下标；h=low,i=0,j=middle+1。h=middle&j=highNi+Y前段元素小于后段元素Y前段元素存入数组AN后

4、段元素存入数组B转存最后元素将数组 B 中元素依次复制到A 中END返回五、算法设计分析选择排序k，将数组第一个元素赋给kk xj（j=i+1；jn；j+）k 替换;否则，不替换。将每次选好的最小元素，按顺序放在已经排好的数列最后。最终，完成数据排列。起泡排序x，比较xi(i=0；in-1；i+)xj（j=i+1；jn；j+）大小，其xi与xj2 for 达到把乱序数据，实现由小到大的排列。快速排序定义数组 x，变量i、j、k，选取参照k=x(i+j)/2，从左到右找比键值k 大的元素，从右到左找比键值 k 小的元素，将找到且满足条件的元素进行交换。由上述过程，把比键值k 大的元素存入大数组，

5、比键值k 小的元素存入小数k 完成排序。合并排序highlowmiddleh 为后段下标，h=low，i=0，j=middle+1；xhxj,h=middle&j=highA六、源代码#include stdio.h #include time.h #include malloc.h #include stdlib.hvoid selectsort(int *x,int n)/选择排序int i,j,k,temp; for(i=0;in-1;i+)k=i;k */for(j=i+1;jxj) k=j;/*k if(i!=k)k!=i 是才交换，否则xi*/temp=xi;xi=xk;/*xix

6、k*/xk=temp;void bubble(int *x,int n)*/起泡排序int i,j,temp; for(i=0;in-1;i+)for(j=i+1;jxj)xixj*/temp=xi;xi=xj; xj=temp;void quick(int *x,int i,int j) /快速排序int m,n,temp; int k;m=i; n=j;k=x(i+j)/2;*/dowhile(xmk&mk&ni) n-;/* 从右到左找比k 小的元if(m=n)*/temp=xm; xm=xn; xn=temp; m+;n-;while(m=n);if(mi) quick(x,i,n);

7、void merge(int x,int low,int middle,int high) /合并排序/高位high，低位low，中位middleint h,i,j,k;int y30000; h=low; i=low; j=middle+1;while(h=middle&j=high)if(xhmiddle) for(k=j;k=high;k+)yi=xk; i+;elsefor(k=h;k=middle;k+)yi=xk; i+;for(k=low;k=high;k+)xk=yk;void mergesort(int x,int low,int high) /合并排序函数的具体实现int

8、middle; if(lowhigh)middle=(low+high)/2;/middle mergesort(x,low,middle);mergesort(x,middle+1,high); merge(x,low,middle,high);int main()srand(time(NULL); int i,x3000,n=3000;float start,end;/ 结束时间for( i=0;i3000;i+) xi=rand()%5000; start=(float)clock(); selectsort(x,3000); end=(float)clock();printf(选择排序

9、，所需时间:%.f 毫秒n,(end-start);for( i=0;i3000;i+) xi=rand()%5000; start=(float)clock(); bubble(x,3000); end=(float)clock();printf(起泡排序，所需时间:%.f 毫秒n,(end-start);for( i=0;i3000;i+) xi=rand()%5000; start=(float)clock(); quick(x,0,n-1); end=(float)clock();printf(快速排序，所需时间:%.f 毫秒n,(end-start);for( i=0;i3000;i

10、+) xi=rand()%5000; start=(float)clock(); mergesort(x,0,n-1); end=(float)clock();printf(合并排序，所需时间:%.f 毫秒n,(end-start);return 0;七、运行结果分析选择排序，所需时间：11起泡排序，所需时间：27快速排序，所需时间：0 O n2选择排序时间复杂度：平均O n2，最好O n2，最坏起泡排序时间复杂度：平均O n2 O n2 O nlogOnOnOlog快速排序时间复杂度：平均2，最好2，最坏loglogOnOnOnloglog合并排序时间复杂度：平均2，最好2，最坏2O由以上分析