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

《《算法分析与设计》排序问题的答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、体有序序列。四、算法的流程图选择排序待排序数据元素将数组第一个数设为键值返回，继续进行上一步扫描数组中最小的元素将每趟最小元素，存入数组得到排序好的数组开始，令i=0，j=i+1起泡排序x[i]>x[j]是否temp=x[i]x[i]=x[j]x[j]=tempi=ji>n否结束是快速排序得到需合并的数组设数组第一个为键值得到后一个数与键值比较存入大数组存入小数组将小数组，键值，大数组连在原数组中大小数组分别递归合并排序开始，高位high，低位low，中点middleh为前段下标，j为后段下标；h=low,i=0,j=middle+1。h<=middle&&j<=highNY前段元素小于后段元

4、素转存最后元素将数组B中元素依次复制到A中N后段元素存入数组B前段元素存入数组AENDYi++返回五、算法设计分析选择排序定义变量k，将数组第一个元素x[0]（i=0；ix[j]，则将二者进行大小交换，否则不交换。通过2个for

5、循环，最终实现所有相邻数据进行比较，从第一对到最后一对。达到把乱序数据，实现由小到大的排列。快速排序定义数组x，变量i、j、k，选取参照k=x[(i+j)/2]，从左到右找比键值k大的元素，从右到左找比键值k小的元素，将找到且满足条件的元素进行交换。由上述过程，把比键值k大的元素存入大数组，比键值k小的元素存入小数组。对两部分数组的元素和键值k放回原数组，再次利用上述方法，运用递归，完成排序。合并排序首先，定义高位high，地位low，中点middle；开始，令h为前段下标，j为后段下标，h=low，i=0，j=middle+1；当h<=middle&&j<=high，如果x[h]

6、将前段元素存入数组A，否则，将后段元素存入数组B；当h<=middle&&j<=high不成立，转存最后元素，将数组B中的元素依次复制到A中。六、源代码#include"stdio.h"#include"time.h"#include"malloc.h"#include"stdlib.h"voidselectsort(int*x,intn)//选择排序{inti,j,k,temp;for(i=0;ix[j])k=j;/*k总是指向最小元素*/if(i!=k){/*当k!=i是才交换，否则x[i]

7、即为最小*/temp=x[i];x[i]=x[k];/*x[i]与x[k]进行交换*/x[k]=temp;}}}voidbubble(int*x,intn)/*定义两个参数：数组首地址与数组大小*///起泡排序{inti,j,temp;for(i=0;ix[j])/*将x[i]与x[j]，