《几种排序算法的平均性能比较(实验报告).doc》由会员分享，可在线阅读，更多相关《几种排序算法的平均性能比较(实验报告).doc（7页珍藏版）》请在三一文库上搜索。
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是最小值。首先，如果就！=1,
3、我们交换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 个元素的数列分为已有序和无序两个部分， 每次处理就是将无序数列的第 一个元素与有序数列的元素从后往前逐个进行比较
4、，找出插入位置，将 该元素插入到有序 数列的合适位置中。算法程序实现如下：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;自底向上合并排序： 利用分治法思想， 将两个 (或两个以上) 有序表合并成一个新的有序表， 即把待排序序列分为若干个子序列， 每个子序列是有序的。 然后再把有序子序列合并为整体 有序 序列。 将已有序的子序列合并，得到完全有序的序列； 即先使每个子序列有序， 再使 子序列段
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 (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 BottomupS
6、ort( 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, i
7、nt 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=Alo
8、w;Alow=Ai;Ai=aa;w=i;void Quick( int *A, int low, int high, int &c)int w;if (lowhigh)Split(A,low,high,w,c);Quick(A,low,w-1,c);Quick(A,w+1,high,c);void QuickSort( int *Array, int n, int &c)c=0;Quick(Array,0,n-1,c);堆排序： 堆排序利用了大根堆 ( 或小根堆 ) 堆顶记录的关键字最大 ( 或最小 ) 这一特征， 使得在 当前无序区中选取最大 (或最小 )关键字的记录变得简单。 先将初始文件
9、 R1.n 建成一个大根堆,此堆为初始的无序区， 再将关键字最大的记录 R1（ 即堆顶 ）和无序区的最后一个记录 Rn 交 换 ， 由 此 得 到 新 的 无 序 区 R1.n-1和 有 序 区 Rn ， 且 满 足R1.n- 1.keys Rn.ke y,由于交换后新的根R1可能违反堆性质，故应将当前无序区R仁n-1调整为堆。然 后再次将R1.n-1中关键字最大的记录 R1和该区间的最后一个 记录 Rn-1 交换，由此得到新的无序区 R1.n-2 和有序区 Rn- 1.n ，且仍满足关系R1. n- 2.keys n) return ;while (2*i+1=n & !done)j=i;i
10、=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;选择排序合弄排序，决速排序3286928040&4463270482704-1801246041156622816577771019402运行时间100000生成随机数Siftdow n(AA,j-1,0,c);实验数据及其结果（可用图表形式给出）输入规模nselecti
11、 onin serti onbottomupquickHeap5000运行时间（毫秒）7878000数组兀素比较次数124975006200198568136318310774410000运行时间（毫秒）3122811600数组兀素比较次数499950002520847512365813811123542420000运行时间（毫秒）1263112316016数组兀素比较次数1999900009975063926747630292351081230000运行时间（毫秒）28702527161615数组兀素比较次数44998500022497904141026846028980036640000运
12、行时间（毫秒）52104509471516数组元素比较次数799980000402537541574791663812110117250000运行时间（毫秒）81747004471631数组元素比较次数1249975000626068874733390866351140973420919201920920209202092120922209222092220923209232092420924*209242024209242092420925209252092620927209272Q927209272092720928202&20929汕9292092920930209302002C9302
13、093020530209312093120931209322093220933209332093320933209342093420934209342093420&352093520936209372093720937209372093S2Q93S2094 Q209402094120941209412094120942209432043209432094420945209452094520945209462094620948209482094820949209492049209502095 Q209512095120952209522095320953209542095420955209552
14、09552095520955209552255209562095620957209572095720957209582095820958209592095920959209592095920960209S02096120961209612Q96120962209622 09&22眈2209522095220963209632096320963209632Q964209642Q9672096720&68209682 09&820968209602096920969209692096920970209702097020?71209722097220972209722 0973209732Q9732
15、Q973209742Q974209742097420975209752097520976209762097720977209772097820970209782097820978209792097920980209B1209S1209812098220982209832090420W4209BS20996209B6209862098620986209862098720988209&02Q9S920网2058920990209902099120991209912099220992209922099220W2209922099J20993209032099J20993209932099320994
16、20994209942099520996209962099620998209962099620999Z09992099920999| |同时运行比较次齣实验结果分析及结论：选择排序算法最稳定， 算法的效率只跟输入规模有关， 与元素序列无关， 但也是效率最 差。插入排序的效率跟元素的序列有关， 最好情况 (已排序) 时间复杂度为 0，最坏情况 (逆 序)时间复杂度为E (n2).自底向上合并排序、快速排序、堆排序的效率差不多，最坏情况和 最好情况时间复杂度都为o(n log n),对于绝大部分元素有序的数组，这三种排序算法的效率不如插入排序。实验自我评价及心得体会：通过这次实验， 我对这五种排序的原理和执行过程有了更清楚地了解，由于本次实验是在 VC+2008 平台下利用 MFC 实现，在学习算法的过程中同时也让我更加熟悉了 windows 的界面编程方法。主要参考文献：算法设计技巧与分析 沙特 著