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

实验课程：算法分析与设计 实验名称：几种排序算法的平均性能比较 （验证型实验）实验目标：（1） 几种排序算法在平均情况下哪一个更快。（2） 加深对时间复杂度概念的理解。实验任务：（1）实现几种排序算法（selectionsort, insertionsort,bottomupsort,quicksort, 堆排序）。对于快速分类，SPLIT中的划分元素采用三者A(low)，A(high)，A(low+high)/2)中其值居中者。（2）随机产生20组数据（比如n=5000i，1i20）。数据均属于范围（0，105）内的整数。对于同一组数据，运行以上几种排序算法，并记录各自的运行时间（以毫秒为单位）。（3）根据实验数据及其结果来比较这几种分类算法的平均时间和比较次数，并得出结论。实验设备及环境：PC；C/C+等编程语言。实验主要步骤：(1) 明确实验目标和具体任务；(2) 理解实验所涉及的几个分类算法；(3) 编写程序实现上述分类算法；(4) 设计实验数据并运行程序、记录运行的结果；(5) 根据实验数据及其结果得出结论；(6) 实验后的心得体会。问题分析（包括问题描述、建模、算法的基本思想及程序实现的技巧等）：选择排序：令A1n为待排序数组，利用归纳法，假设我们知道如何对后n-1个元素排序，即对啊An排序。对某个j,1=j=n,设Aj是最小值。首先，如果就！=1，我们交换A1和Aj。然后由假设，已知如何对A2.n排序，因此可对在A2n中的元素递归地排序。可把递归改为迭代。算法程序实现如下：void SelectionSort(int *Array,int n,int &c)int i,j,k;int aa;c=0;for(i=0;in;i+)k=i;for(j=i+1;jn;j+)c+;if(ArrayjArrayk)k=j;if(k!=i)aa=Arrayi;Arrayi=Arrayk;Arrayk=aa;插入排序：将n个元素的数列分为已有序和无序两个部分， 每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将 该元素插入到有序数列的合适位置中。算法程序实现如下：void InsertionSort(int *Array,int n,int &c)int i,j;int aa;c=0;for(i=0;i=0 & Arrayjaa)c+;Arrayj+1=Arrayj;j=j-1;Arrayj+1=aa;自底向上合并排序：利用分治法思想，将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序 序列。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。算法程序实现如下：void Merge(int *A,int p,int q,int r,int &c)int *B=new intr-p+1;int s=p;int t=q+1;int k=0;while(s=q & t=r)c+;if(As=At)Bk=As;s=s+1;elseBk=At;t=t+1;k=k+1;if(s=q+1)while(t=r)Bk=At;k=k+1;t=t+1;else while(s=q)Bk=As;k=k+1;s=s+1;k=0;while(p=r)Ap=Bk;k+;p+;delete B;void BottomupSort(int *Array,int n,int &c)int s,i, t=1;c=0;while(tn)s=t;t=2*s;i=0;while(i+tn)Merge(Array,i,i+s-1,i+t-1,c);i=i+t; if(i+sn)Merge(Array,i,i+s-1,n-1,c);快速排序：设要排序的数组是A0AN-1，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的 数都放到它后面，这个过程称为一趟快速排序。快速排序就是递归调用此过程。算法程序实现如下：void Split(int *A,int low,int high,int &w,int &c)int aa,x;int j,i=low;int mid=(low+high)/2;if(AlowAhigh)if(AmidAlow)w=low;else if(AmidAhigh)w=mid;else w=high;elseif(AmidAhigh)w=high;else if(AmidAlow)w=mid;else w=low;c+;x=Aw;aa=Alow;Alow=Aw;Aw=aa;for(j=low+1;j=high;j+)c+;if(Aj=x)i=i+1;if(i!=j)aa=Ai;Ai=Aj;Aj=aa;aa=Alow;Alow=Ai;Ai=aa;w=i;void Quick(int *A,int low,int high,int &c)int w;if(lown)return;while(2*i+1=n & !done)j=i;i=2*i+1;c=c+2;if(i+1Hi)i=i+1;if(Hj=0;i-)Siftdown(A,n-1,i,c);void HeapSort(int *A,int n,int &c)c=0;MakeHeap(A,n,c);int j;int x;for(j=n-1;j=1;j-)x=A0;A0=Aj;Aj=x;Siftdown(A,j-1,0,c);实验数据及其结果（可用图表形式给出）：输入规模nselectioninsertionbottomupquickHeap5000运行时间（毫秒）7878000数组元素比较次数124975006200198568136318310774410000运行时间（毫秒）3122811600数组元素比较次数499950002520847512365813811123542420000运行时间（毫秒）1263112316016数组元素比较次数1999900009975063926747630292351081230000运行时间（毫秒）28702527161615数组元素比较次数44998500022497904141026846028980036640000运行时间（毫秒）52104509471516数组元素比较次数799980000402537541574791663812110117250000运行时间（毫秒）81747004471631数组元素比较次数12499750006260688747333908663511409734实验结果分析及结论：选择排序算法最稳定，算法的效率只跟输入规模有关，与元素序列无关，但也是效率最差。插入排序的效率跟元素的序列有关，最好情况（已排序）时间复杂度为0，最坏情况（逆序）时间复杂度为(n2).自底向上合并排序、快速排序、堆排序的效率差不多，最坏情况和最好情况时间复杂度都为o(nn),对于绝大部分元素有序的数组