《排序算法的时间性能比较》由会员分享，可在线阅读，更多相关《排序算法的时间性能比较（12页珍藏版）》请在金锄头文库上搜索。
1、排序算法的时间性能比较一、问题描述给出一组实验来比较下列排序算法的时间性能： 快速排序、堆排序、 冒泡排序二、基本要求（1）时间性能包括平均时间性能、最好情况下的时间性能、最差情 况下的时间性能等。（2）实验数据应具有说服力，包括： 规模范围要大（如从100到 10000），数据的初始特性类型要多，因而需要具有随机性； 实 验数据的组数要多，即同一规模的数组要多选几种不同类型的数据来 实验。 实验结果要能以清晰的形式给出，如图、表等。 （3）算法 所用时间必须是机器时间，也可以包括比较和交换元素的次数。 （4）实验分析及其结果要能以清晰的方式来描述，如数学公式或图5）要给出实验的方案及其分析。
2、三、工具/准备工作Microsoft Visual C+ 6.0 软件。、分析与实现1.快速选择排序 这个是冒泡排序的一种改进，他的基本思想就是在当前无序区 R【1.H】中任取一个数据元素的基准用此基准将当前无序区划分成 左右二个较小的无序去区，R【1i-1】和R【i + 1.H】，且左边 的元素序子区中的数据元素均小于等于基数元素，右边的元素序子区 中的数据元素均大于等于基数元素。直到所有无序子区中的数据元素 均已排序为止。2.堆排序堆排序实质上就是具备有如下性质的完全二叉树：树中任一非子叶节 点的关键字均大于等于其子孩子结点的关键字，它只要记录一个大小 的辅助空间，每个待排序的记录只占有一
3、个存储空间，一般记录数较 小的。但对基数较大的文件还是很有效的，因为运行时间主要是小号 在建初始堆和调整建新堆时进行的反复的筛选上的。3.冒泡排序这种排序的比较基本思想就是二二比较待排序的数据元素的大小，发 现二个数据元素的次序相反时候，就进行交换，知道没有反序的数据 为止。冒泡排序是一种一次比较出最小或最大值，然后将其放置序列 的最后一位置，再将剩下的从打一个位置开始到 N-1 的位置进行重 复的操作。排序算法的时间空间复杂度排序方法最坏情况平均情况最好情况快速排序O ( nlogn )0(n2)O堆排序O(nlogn)O(nlogn)O(n)冒泡排序0( nJO(nlogn)O(n)程序代
4、码：#include#include #include #define MAXSIZE 50 typedef int KeyType;#define MAXNUM 100 typedef structKeyType Key; RedType;RedType RMAXNUM; typedef structRedType rMAXSIZE+1; int length;Sqlist;Sqlist L,L0,L1,L2,L3,L4,L5,L6,L7; typedef Sqlist HeadType; #define RADIX 10 #define MAX 8#define MAX_SPACE 100
5、00typedef int KeysType; typedef struct KeysType Keys MAX;int next;SLCell;typedef struct SLCell rlMAX_SPACE;int Keynum;int recnum;SLList;typedef int ArrTypeRADIX;int compare8;int change8;void shuRu(Sqlist L)int i=1,n;printf(请输入你输入的数据个数:n); scanf(%d,&n);printf(请依次的输入各个数据值n);L.length=n;for(;i=L.length;
6、i+)scanf (%d,&L.ri);void shuChu(Sqlist L)int i=1;printf (该顺序存储中的数据元素为：); for(;iL.length;i+)printf(%d,L.ri); printf(%dnn,L.ri);/=快速排序=int partition (Sqlist L,int low ,int high) KeyType pivotKey;L.r0=L.rlow;pivotKey=L.rlow.Key;change 4+;while (lowhigh)compare4+;compare4+;while (low=pivotKey) -high;com
7、pare4+;L.rlow=L.rhigh;change4+;compare4+;while (lowhigh&L.rlow.Key=pivotKey) +low;compare 4+;L.rhigh=L.rlow;change4+;L.rlow=L.r0;change 4+; return low; void Qsort (Sqlist L,int low,int high) int pivotloc;if (lowhigh) pivotloc =partition (L,low,high);Qsort (L,low,pivotloc-1);Qsort (L,pivotloc+1,high)
8、; void QuickSort (Sqlist L) Qsort(L,1,L.length); /=堆排序= void HeadAdjust(HeadType H,int s,int m)RedType rc;int j;rc=H.rs;for( j=2*s;j=m;j*=2) compare5+;if(jm&(compare5+)&(H.r j.KeyH.rj.Key)compare5+;break; H.rs=H.rj;s=j;change5+;H.rs=rc; change5+; void HeadSort (HeadType H) RedType temp;for(int i = H
9、.length/2 ; i0; -i) compare 5+;HeadAdjust (H,i,H.length); for(i=H.length;i1;i-) compare 5+;temp=H.r1;H.r1=h.ri;h.ri=temp; change5+=3HeadAjust (H,1,i-1); /=冒泡法排序= void bubbleSort (Sqlist &L) int i,j,temp; for(i=1,iL.j+1.Key0;L.rj=1.Key=temp; charge2+=3pri ntf(t请选择你要进行的操作tn);printf(tcase 1:产生完全随机的数据再进
10、行排序tn);printf(tcase 2:自行输入一些数据再实现排序操作tn);printf(tcase 0:退出程 序tn);void Tableprintf(t=算法名称= = = =比较次数= = = =交换次数= = = = = = printf(t1 快速排 序 t%dt %dtn,COMPAREH change 5);printf(t=算法名称= = = =比较次数= = = =交换次数= = = = = = printf(t1 堆排序 t%dt %dtn,COMPAREH change3);printf(t=算法名称= = = =比较次数= = = =交换次数= = = = =
11、 = printf(t1 冒泡排 序 t%dt %dtn,COMPAREH change 0);void Random (sqlist &L) SLList LK;for (int i=0;i8;i+)comparei=0changei=0printf (请输入你产生的随机数的数据个数：”)printf(排序之前的随机数的d个数是：n：L.length);for(i=1;i=L.length:i+)printf (%d,L.ri.key);printf(n下面执行的各个排序的运行情况、你“);void mian()int choose;Men();printf(t 请选择:)；scanf (c
12、hoose)case 1:Random (L);break:case 2:Yonghu (L);break:case 3:Nixh (L);break:case 0; return;五、测试与结论输入数据得出结果如下：1当要求随机生成十二个数的结果如下：g ,.口,國讲，肠ram Fi ：x9&Microsaft Visual StudioMyPro ects5j4j644Debug54644,-eh请输加临扎的轉个数: 舊依执的输入容个数据值bfe2 4 Ibt 21W 2J2 bHU LM2febbV丁丹 SVbiZIn: 102 210 232 475 54Q 5G2 536 3J5 1
13、023 13?5 CG57 旦灶母払比较我数= = = =交换软数= = = = =34701111442.但随机生成34个数的结果如下:C:Program Files (x86)IMicrosoft Visual StudioMyProyects4r5Debug4r5.e:e请输AWA的数据个数:34请依秋的输入各个数据佰10E 276 1021 5210 437 3524 8973 121 211 1524 5384 528 3846 9254 136 289 1636 597 2 5761451VZ7 543 S473V75 mb IB?瓯tJ7BV5 V6K 沁謂该I页底冇储元素为；10G 121 13G 14G 187 208 211 232 27t 299 437 52S 59G G17 9G0 13) 21 1524 1836 1927 1993 3218 3524 384654 9875 99363975 4523 5210 5384 5972 6423 7895 8973 92目序进比较欣数砒02991156交换秋数13224116G3结论：从数据结果我们可以看出，当排序的数据个数少的时候，快速 排序是最快的，而大的数据时，堆排序是比较好的选择。每一个排序 都有它自己的特点。
