《《算法分析与设计》排序问题的答案》由会员分享，可在线阅读，更多相关《《算法分析与设计》排序问题的答案（8页珍藏版）》请在金锄头文库上搜索。
1、题一 排序问题一、 设计目的1掌握各种排序的基本思想。2 掌握各种排序方法的算法实现。3掌握各种排序方法的优劣分析及花费的时间的计算。 4掌握各种排序方法所适应的不同场合。二、 设计内容和要求利用随机函数产生3000 个随机整数，利用选择排序、起泡排序、快速排序、合并排序 （归并排序）等排序方法进行排序，并统计每一种排序上机所花费的时间。参考答案一、题一（排序问题）二、运行环境（软、硬件环境）编写程序：C语言编译环境： VC+6.0软件： Windows7 64 位 硬件：华硕 PC 机三、算法设计的思想 选择排序： 每一趟，从待排序的数据元素中，选出最小的一个元素，按顺序放在已排好 序的数列
2、的最后，直到全部待排序的数据元素排完。最终实现数据元素从小到大的排序。起泡排序： 一次比较两个相邻的元素，如果第一个元素比第二个元素大，就将他们排序 进行交换。通过不断对要排序的数列走访，依次比较相邻两个元素大小，从开始的第一 对到结尾的最后一对。最终完成数据从小到大的排序。快速排序： 通过一趟排序，将要排序的数据分成独立的两部分，其中一部分的所有数据 都比另外一部分的所有数据都要小。再按上述方法对这两部分数据，分别进行快速排序，整个排序过程可以递归 进行，以此达到整个数据变成有序序列。合并排序： 将两个及两个以上有序表，合并成一个新的有序表。 即把待排序序列分为若干个子序列，每个子序列是有序
3、的。然后再把有序子 序列合并在一起，形成整体有序序列。四、算法的流程图选择排序待排序数据元素将数组第一个数设为键值返回，继续进行上一步扫描数组中最小的元素将每趟最小元素，存入数组起泡排序temp=xi xi=xj xj=temp得到排序好的数组i=j快速排序存入大数组合并排序i+前段兀素存入数组A后段兀素存入数组B返回V开始，高位high,低位low,中点middleh为前段下标，j为后段下标; h=low,i=0,j=middle+l。hv=middle&jv=high前段元素小于后段兀素五、算法设计分析选择排序定义变量k,将数组第一个元素x0 （i=0； ivn-1； i+）赋给k,将k与
4、数组 其他元素xj （j=i+1； jxj,则将二者进行大小交换，否则不交换。通过2个for循环，最终实现所有相邻数据进行比较，从第一对到最后一对。 达到把乱序数据,实现由小到大的排列。快速排序定义数组x,变量i、j、k,选取参照k=x（i+j）/2,从左到右找比键值k大的 元素，从右到左找比键值k小的元素，将找到且满足条件的元素进行交换。由上述过程，把比键值k大的元素存入大数组，比键值k小的元素存入小数 组。对两部分数组的元素和键值k放回原数组，再次利用上述方法，运用递归， 完成排序。合并排序首先，定义高位high，地位low，中点middle；开始，令h为前段下标，j 为后段下标， h=l
5、ow， i=0， j=middle+1；当h二middle&j二high,如果xhxj) k=j;if(i!=k)temp=xi;xi=xk;xk=temp;/选择排序/*给记号 k 赋值*/*k 总是指向最小元素*/*当k!=i是才交换，否则xi即为最小*/*xi与xk进行交换*/void bubble(int *x,int n)/起泡排序int i,j,temp;for(i=0;in-1;i+) for(j=i+1;jxj)temp=xi;xi=xj;xj=temp;/*定义两个参数：数组首地址与数组大小*/*注意循环的起始和终止值，即上下限*/*将xi与xj，进行大小交换*/*通过大小比
6、较，每次选取一个最小值*/void quick(int *x,int i,int j) /快速排序 int m,n,temp;int k; m=i; n=j; k=x(i+j)/2;do while(xmk&mk&ni) n-; if(m=n) temp=xm; xm=xn; xn=temp; m+; n-; while(m=n); if(mi) quick(x,i,n);/*选取的参照*/*从左到右找比k大的元素*/ /*从右到左找比k小的元素*/*找到且满足条件，则交换*/*运用递归*/void merge(int x,int low,int middle,int high) /合并排序高
7、位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 middle;if(lowhigh)middle=(low+high)/2;/中位 middle 的取值mergeso
8、rt(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(选择排序，所需时间:.f毫秒n,(end-start);for( i=0;i3000;i+)xi=rand
9、()%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+)xi=rand()%5000; start=(float)clock(); mergesort(x,0,n-1
10、); end=(float)clock();printf(”合并排序，所需时间:.f毫秒n,(end-start);return 0;七、运行结果分析 选择排序，所需时间：11毫秒 起泡排序，所需时间：27毫秒 快速排序，所需时间：0毫秒 合并排序，所需时间：13毫秒选择排序时间复杂度：平均 最好 最坏起泡排序时间复杂度：平均 2),最好 ),最坏 )快速排序时间复杂度：平均 lOg2必最好 lOg2必最坏 CJ合并排序时间复杂度：平均 lOg2必 最好 lOg2必 最坏 lOg2丿由以上分析可知，选择排序、起泡排序的时间复杂度均为0 CO，选择排序 较好；快速排序、归并排序时间复杂度为 ( lOg2其中快速排序较好。八、收获及体会经过排序题目训练,对选择排序、起泡排序、快速排序、合并排序的概念、 思想以及算法，都有了深入理解和自己的看法。对于for、while和do while 循环，if else判断，递归调用，也运用的更加得心应手，提升自己编程能力。由选择排序、起泡排序、快速排序、合并排序的复杂多对比,可知快速排序较好与其他排序(在n值比较大时)。选择排序、起泡排序的时间复杂度均为 CO，选择排序较好；快速排序、归并排序时间复杂度为 ( lOg2 I其中快速排序较好。
