几种排序算法的平均性能比较(实验报告).doc

《几种排序算法的平均性能比较(实验报告).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、..实验课程：算法分析与设计实验名称：几种排序算法的平均性能比较（验证型实验）实验目标：（1）几种排序算法在平均情况下哪一个更快。（2）加深对时间复杂度概念的理解。实验任务：（1）实现几种排序算法（selectionsort,insertionsort,bottomupsort,quicksort,堆排序）。对于快速分类，SPLIT中的划分元素采用三者A(low)，A(high)，A((low+high)/2)中其值居中者。（2）随机产生20组数据（比如n=5000i，1≤i≤20）。数据均属于围（0，105）的整数。对于同一组数据，运行以上几种排序算法，并记录各自的运行时间（以毫秒

2、为单位）。（3）根据实验数据及其结果来比较这几种分类算法的平均时间和比较次数，并得出结论。实验设备及环境：PC；C/C++等编程语言。实验主要步骤：(1)明确实验目标和具体任务；(2)理解实验所涉及的几个分类算法；(3)编写程序实现上述分类算法；(4)设计实验数据并运行程序、记录运行的结果；(5)根据实验数据及其结果得出结论；(6)实验后的心得体会。问题分析（包括问题描述、建模、算法的基本思想及程序实现的技巧等）：选择排序：令A[1…n]为待排序数组，利用归纳法，假设我们知道如何对后n-1个元素排序，即对啊[A…n]排序。对某个j,1<=j<=n,设A[j]是最小值。首先，如果就！=

3、1，我们交换A[1]和A[j]。然后由假设，已知如何对A[2..n]排序，因此可对在A[2…n]中的元素递归地排序。可把递归改为迭代。算法程序实现如下：voidSelectionSort(int*Array,intn,int&c){inti,j,k;intaa;c=0;for(i=0;i

4、是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。算法程序实现如下：voidInsertionSort(int*Array,intn,int&c){inti,j;intaa;c=0;for(i=0;i=0&&Array[j]>aa){c++;Array[j+1]=Array[j];j=j-1;}Array[j+1]=aa;}}自底向上合并排序：利用分治法思想，将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的

5、。然后再把有序子序列合并为整体有序序列。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。算法程序实现如下：.....voidMerge(int*A,intp,intq,intr,int&c){int*B=newint[r-p+1];ints=p;intt=q+1;intk=0;while(s<=q&&t<=r){c++;if(A[s]<=A[t]){B[k]=A[s];s=s+1;}else{B[k]=A[t];t=t+1;}k=k+1;}if(s==q+1){while(t<=r){B[k]=A[t];k=k+1;t=t+1;}}else{whi

6、le(s<=q){B[k]=A[s];k=k+1;s=s+1;}}k=0;while(p<=r){A[p]=B[k];.....k++;p++;}deleteB;}voidBottomupSort(int*Array,intn,int&c){ints,i,t=1;c=0;while(t

7、作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。快速排序就是递归调用此过程。算法程序实现如下：voidSplit(int*A,intlow,inthigh,int&w,int&c){intaa,x;intj,i=low;intmid=(low+high)/2;if(A[low]