排序算法的时间性能比较

1、排序算法的时间性能比拟一、问题描述给出一组实验来比拟以下排序算法的时间性能：快速排序、堆排序、冒泡排序二、根本要求1时间性能包括平均时间性能、最好情况下的时间性能、最差情 况下的时间性能等。2 实验数据应具有说服力，包括：规模围要大如从100到10000,数据的初始特性类型要多，因而需要具有随机性；实验数据的组数要多，即同一规模的数组要多项选择几种不同类型的数 据来实验。 实验结果要能以清晰的形式给出，如图、表等。3算法所用时间必须是机器时间，也可以包括比拟和交换元素的次数。4实验分析与其结果要能以清晰的方式来描述，如数学公式或图 表等。5要给出实验的方案与其分析。三、工具/准备工作Micro

2、soft Visual C+ 6.0 软件。四、分析与实现1. 快速选择排序这个是冒泡排序的一种改良，他的根本思想就是在当前无序区R1.H中任取一个数据元素的基准用此基准将当前无序区划分成左右二个较小的无序去区， R1i-1和Ri+1.H,且左边的 元素序子区中的数据元素均小于等于基数元素， 右边的元素序子区中 的数据元素均大于等于基数元素。直到所有无序子区中的数据元素均已排序为止。2. 堆排序堆排序实质上就是具备有如下性质的完全二叉树：树中任一非子叶节 点的关键字均大于等于其子孩子结点的关键字， 它只要记录一个大小 的辅助空间，每个待排序的记录只占有一个存储空间， 一般记录数较 小的。但对基

3、数较大的文件还是很有效的， 因为运行时间主要是小号 在建初始堆和调整建新堆时进行的反复的筛选上的。3. 冒泡排序这种排序的比拟根本思想就是二二比拟待排序的数据元素的大小， 发 现二个数据元素的次序相反时候，就进行交换，知道没有反序的数据 为止。冒泡排序是一种一次比拟出最小或最大值，然后将其放置序列 的最后一位置，再将剩下的从打一个位置开始到 N-1的位置进行重复 的操作。排序算法的时间空间复杂度排序方法最坏情况平均情况最好情况快速排序O( nlogn)0(n2)0(1)堆排序0( nlogn)0( nlogn)0(n)冒泡排序0(n2)0( nlogn)0(n)程序代码：#in clude&l

4、t;stdio.h>#in clude<stdlib.h> #in clude<math.h> #defi ne MAXSIZE 50 typedef int KeyType;#defi ne MAXNUM 100typedef structKeyType Key; RedType;RedType RMAXNUM;typedef structRedType rMAXSIZE+1;int len gth;Sqlist;Sqlist L, L0,L1,L2, L3,L 4, L5,L6丄7; typedef Sqlist HeadType;#defi ne RADIX

5、 10#defi ne MAX 8#defi ne MAX_SPACE 10000 typedef int KeysType;typedef structKeysType Keys MAX;int n ext;SLCell;typedef struct SLCell rlMAX_SPACE;int Keynum;int recnu m;SLList;typedef int ArrTypeRADIX;int compare8;int cha nge8;void shuRu(Sqlist L)int i=1, n;printf("请输入你输入的数据个数：n");sca nf(&

6、quot;%d",&n);printf(请依次的输入各个数据值n");Len gth 二n;for(;i<=Len gth;i+)sca nf ("%d",&L.ri);void shuChu(Sqlist L)int i=1;printf ("该顺序存储中的数据元素为：");for(;i<L.le ngth;i+)pri ntf("%d",L.ri); prin tf("%dnn" ,L .ri);二=快速排序=int partiti on (Sqlist L,i

7、nt low ,int high) KeyType pivotKey;L.r0=L.rlow;pivotKey=L.rlow.Key;cha nge 4+;while (low<high)compare4+;compare4+;while (low<high&&L.rhigh.Key>=pivotKey)-high;compare4+;L.rlow=L.rhigh;cha nge4+;compare4+;while (low<high&&L.rlow.Key<=pivotKey)+low;compare 4+;L.rhigh=L.r

8、low;cha nge4+;L.rlow=L.r0;cha nge 4+;return low;void Qsort (Sqlist L,i nt low,i nt high) int pivotloc;if (lowvhigh) pivotloc =partition (L,low,high);Qsort (L,low,pivotloc-1);Qsort (L,pivotloc+1,high);void Quicksort (Sqlist L)Qsort(L,1,L.le ngth);/=堆排序=void HeadAdjust(HeadType H,i nt s,i nt m)RedType

9、 rc;int j;rc=H.rs;for(j=2*s;jv=m;j*=2) compare5+;if(jvm&&(compare5+)&&( H.rj.Key<H.rj+1.Key)+j;if(rc.Key>H.rj.Key)compare5+;break;H.rs=H.rj;s=j;cha nge5+;H.rs=rc;cha nge5+; void HeadSort (HeadType H) RedType temp;for(i nt i = H.le ngth/2 ; i>0; -i)compare 5+;HeadAdjust (H,i,

10、H.le ngth);for(i=H.le ngth;i>1;i-)compare 5+;temp二H.r1;H.r1=h.ri;h.ri=temp;cha nge5+=3HeadAjust (H,1,i-1);/=冒泡法排序=void bubbleSort (Sqlist &L) int i,j,temp;for(i=1,i<=Len gth;i+)compare2+;compare2+;if(L.rj.Key>L.j+1.KeyO;L.rj=1.Key=temp;charge2+=3printf("t请选择你要进行的操作tn");prin tf

11、("tcase 1:产生完全随机的数据再进行排序tn");prin tf("tcase 2:自行输入一些数据再实现排序操作tn");printf("tcase 0:退出程序 tn");void Tableprin tf("t二算法名称=比拟次数=交换次数=prin tf("t1快速排序 t%dt %dt n",COMPAREH cha nge5)；prin tf("t=算法名称=比拟次数=交换次数=prin tf("t1堆排序 t%dt %dtn",COMPAREH cha

12、nge3);prin tf("t=算法名称=比拟次数=交换次数=prin tf("t1冒泡排序 t%dt %dt n",COMPAREH cha nge0);void Ran dom (sqlist &L) SLList LK;for (int i=0;i<8;i+)comparei=0cha ngei=0printf ("请输入你产生的随机数的数据个数：)printf("排序之前的随机数的个数是：n',L.length);for(i=1;i<=Len gth:i+)printf ("%d",L.

13、ri.key);prin tf("n下面执行的各个排序的运行情况、你“)；void mia n()int choose;Me n();printf("t请选择：)；seanf(choose)case 1:Ra ndom (L);break:case 2:Yon ghu (L);break:case 3:Nixh (L);break: case 0;return;五、测试与结论输入数据得出结果如下：1当要求随机生成十二个数的结果如下:序请依據册输人督个敎据佰血2 石码 7阳 211 23 bUU 1S2 L3V bS? 102J 4 HYb该1师序弃倩册却拯礼壬为 102 213 2J2攻巧549 SG2 580 875 1023 1395 CC57聲聶 p栅一交换说1O：序法?00