排序算法的时间性能比较

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）O(n2)O(1)堆排序O(nlogn)O(nlogn)O(n)冒泡排序O(n2)O(nlogn)O(n)程序代码：#include#inclu

4、de#include#define MAXSIZE 50typedef int KeyType;#define MAXNUM 100typedef 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 10000typedef int KeysType;ty

5、pedef structKeysType 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;i+)scanf (%d,&L.ri);void s

6、huChu(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;compare4+;L.rlow=L.rhigh;change

7、4+;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);void QuickSort (Sqlist L)Qsort

8、(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.rj.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.length/2 ; i0; -i)compare 5+;HeadAdjus

9、t (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+=3printf(t请选择你要进行的操作tn);printf(tcase 1:产生完全随机的数据再进行排序tn);printf(tcase 2:自行输入一些数据再实现排序操作tn);printf(

10、tcase 0:退出程序tn);void Tableprintf(t=算法名称=比较次数=交换次数=printf(t1 快速排序 t%dt %dtn,COMPAREH change 5);printf(t=算法名称=比较次数=交换次数=printf(t1 堆排序 t%dt %dtn,COMPAREH change 3);printf(t=算法名称=比较次数=交换次数=printf(t1 冒泡排序 t%dt %dtn,COMPAREH change 0);void Random (sqlist &L) SLList LK;for (int i=0;i8;i+)comparei=0changei=

11、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 (choose)case 1:Random (L);break: case 2:Yonghu (L);break: case 3:Nixh (L);break:case 0;return;五、测试与结论输入数据得出结果如下：1当要求随机生成十二个数的结果如下：2.但随机生成34个数的结果如下：结论：