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

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

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

3、小值。首先，如果就！=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;i<n;i+)k=i;for (j=i+1;j<n;j+)c+;if (Arrayj<Arrayk)k=j;if (k!=i)aa=Arrayi;Arrayi=Arrayk;Arrayk=aa;插入排序：将 n 个元素的数列分为已有序和无序两个部分， 每次处理就是将

4、无序数列的第 一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将 该元素插入到有序 数列的合适位置中。算法程序实现如下：void InsertionSort( int *Array, int n, int &c)int i,j;int aa;c=0;for (i=0;i<n;i+)aa=Arrayi;j=i-1;while (j>=0 && Arrayj>aa)c+;Arrayj+1=Arrayj;j=j-1;Arrayj+1=aa;自底向上合并排序： 利用分治法思想， 将两个 (或两个以上) 有序表合并成一个新的有序表， 即把待排序序列分

5、为若干个子序列， 每个子序列是有序的。 然后再把有序子序列合并为整体 有序 序列。 将已有序的子序列合并，得到完全有序的序列； 即先使每个子序列有序， 再使 子序列段间有序。算法程序实现如下：void Merge( int *A, int p, int q, int r, int &c)int *B= new int r-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

6、(t<=r)Bk=At;k=k+1; t=t+1;elsewhile (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 (t<n)s=t;t=2*s;i=0;while (i+t<n)Merge(Array,i,i+s-1,i+t-1,c);i=i+t;if (i+s<n)Merge(Array,i,i+s-1,n-1,c);快速排序：设要排序

7、的数组是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 (Alow<Ahigh)if (Amid<Alow)w=low;else if (Amid<Ahigh)w=mid;else w=high;elseif (

8、Amid<Ahigh)w=high;else if (Amid<Alow)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 (low<high)Split(A,low,high,w,c);Quick(A,low,w-

9、1,c);Quick(A,w+1,high,c);void QuickSort( int *Array, int n, int &c)c=0;Quick(Array,0,n-1,c);堆排序： 堆排序利用了大根堆 ( 或小根堆 ) 堆顶记录的关键字最大 ( 或最小 ) 这一特征， 使得在 当前无序区中选取最大 (或最小 )关键字的记录变得简单。 先将初始文件 R1.n 建成一个大根堆,此堆为初始的无序区， 再将关键字最大的记录 R1（ 即堆顶 ）和无序区的最后一个记录 Rn 交 换 ， 由 此 得 到 新 的 无 序 区 R1.n-1和 有 序 区 Rn ， 且 满 足R1.n- 1.

10、keys < Rn.ke y,由于交换后新的根R1可能违反堆性质，故应将当前无序区R仁n-1调整为堆。然 后再次将R1.n-1中关键字最大的记录 R1和该区间的最后一个 记录 Rn-1 交换，由此得到新的无序区 R1.n-2 和有序区 Rn- 1.n ，且仍满足关系R1. n- 2.keys < R n-1. n .keys，同样要将R1. n-2 调整为堆。 直到无序区只有一个元素为止。void Siftdown( int *H, int n, int i, int &c) bool done= false ;int j,a;if (2*i+1>n) return

11、;while (2*i+1<=n && !done)j=i;i=2*i+1;c=c+2;if (i+1<=n && Hi+1>Hi)i=i+1;if (Hj<Hi)a=Hi;Hi=Hj;Hj=a;else done=true ;void MakeHeap(int *A, int n, int &c)int i;for (i=(n-2)/2;i>=0;i-)Siftdown(A,n-1,i,c);void HeapSort( int *A, int n, int &c)c=0;MakeHeap(A,n,c);int j

12、;int x;for (j=n-1;j>=1;j-)x=A0;A0=Aj;Aj=x;选择排序合弄排序，决速排序3286928040&4463270482704-1801246041156622816577771019402运行时间100000生成随机数Siftdow n(AA,j-1,0,c);实验数据及其结果（可用图表形式给出）输入规模nselecti onin serti onbottomupquickHeap5000运行时间（毫秒）7878000数组兀素比较次数124975006200198568136318310774410000运行时间（毫秒）3122811600数组兀

13、素比较次数499950002520847512365813811123542420000运行时间（毫秒）1263112316016数组兀素比较次数1999900009975063926747630292351081230000运行时间（毫秒）28702527161615数组兀素比较次数44998500022497904141026846028980036640000运行时间（毫秒）52104509471516数组元素比较次数799980000402537541574791663812110117250000运行时间（毫秒）81747004471631数组元素比较次数12499750006260

14、68874733390866351140973420919201920920209202092120922209222092220923209232092420924*209242024209242092420925209252092620927209272Q927209272092720928202&20929汕92920929209302093020«02C9302093020530209312093120931209322093220933209332093320933209342093420934209342093420&3520935209362093720

15、93720937209372093S2Q93S2094 Q209402094120941209412094120942209432043209432094420945209452094520945209462094620948209482094820949209492049209502095 Q20951209512095220952209532095320954209542095520955209552095520955209552255209562095620957209572095720957209582095820958209592095920959209592095920960209

16、S02096120961209612Q96120962209622 09&22眈2209522095220963209632096320963209632Q964209642Q9672096720&68209682 09&820968209602096920969209692096920970209702097020?71209722097220972209722 0973209732Q9732Q973209742Q974209742097420975209752097520976209762097720977209772097820970209782097820978

17、209792097920980209B1209S1209812098220982209832090420W4209BS20996209B6209862098620986209862098720988209&02Q9S920网2058920990209902099120991209912099220992209922099220W2209922099J20993209032099J2099320993209932099420994209942099520996209962099620998209962099620999Z09992099920999| |同时运行比较次齣实验结果分析及结论：选择排序算法最稳定， 算法的效率只跟输入规模有关， 与元素序列无关， 但也是效率最 差。插入排序