排序算法地时间性能比较

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)0(1)堆排序0( nlogn)0( nlogn)0(n)冒

4、泡排序0(n2)0( nlogn)0(n)程序代码:#in clude<stdio.h>#in clude<stdlib.h>#in clude<math.h>#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 S

5、qlist HeadType; #define RADIX 10#define MAX 8#define MAX_SPACE 10000typedef int KeysType;typedef 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(" 请输入你输入

6、的数据个数 : n"); scanf("%d",&n);printf(" 请依次的输入各个数据值 n");L.length=n;for(;i<=L.length;i+)scanf ("%d",&L.ri);void shuChu(Sqlist L)int i=1;printf (" 该顺序存储中的数据元素为： ");for(;i<L.length;i+)printf("%d",L.ri);printf("%dnn",L.ri);/=快速排

7、序 =int partition (Sqlist L,int low ,int high) KeyType pivotKey;L.r0=L.rlow;pivotKey=L.rlow.Key;change 4+;while (low<high)compare4+;compare4+;while (low<high&&L.rhigh.Key>=pivotKey)-high;compare4+;L.rlow=L.rhigh;change4+;compare4+;while (low<high&&L.rlow.Key<=pivotKey)+

8、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 (low<high) pivotloc =partition (L,low,high);Qsort (L,low,pivotloc-1);Qsort (L,pivotloc+1,high); void QuickSort (Sqlist L) Qsort(L,1,L.length); /=堆排序= void HeadAdjust(Hea

9、dType H,int s,int m) RedType rc;int j; rc=H.rs;for(j=2*s;j<=m;j*=2) compare5+;if(j<m&&(compare5+)&&(H.rj.Key<H.rj+1.Key)+j; if(rc.Key>H.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 ; i>

10、0; -i)compare 5+;HeadAdjust (H,i,H.length); for(i=H.length;i>1;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,i<=L.length;i+)compare2+;compare2+;if(L.rj.Key>L.j+1.Key0;L.rj=1.Key=temp;charge2+=3printf

11、("t 请选择你要进行的操作 tn");printf("tcase 1: 产生完全随机的数据再进行排序 tn");printf("tcase 2: 自行输入一些数据再实现排序操作 tn"); printf("tcase 0:退出程序 tn");void Tableprintf("t=算法名称 =比较次数 =交换次数 =printf("t1 快速排序 t%dt %dtn",COMPAREH change 5);printf("t=算法名称 =比较次数 =交换次数 =printf

12、("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;i<8;i+)comparei=0changei=0printf (" 请输入你产生的随机数的数据个数： ”)printf("排序之前的随机数的并数是：n',L.length);for(

13、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当要求随机生成十二个数的结果如下：标准文档请输人你输入的数据个数； 特依次的输入各个

14、数据値562£46 3GG 210232 580 102 13951022 47t眩顺序存:储的数据元章为：102 21U 23Z羽5 548 562 580 895 1B23 1395 6657，交换次数3470ill憾綁序法2但随机生成34个数的结果如下: ' *C:Prcigrami Files (m8GjXMicroso: V sual StudioMyProjects4r5Debijg4r5.exe请输人你输人的数据个数：34请依次的输入各个数据值106 2?6 1021 5219 437 3524 8?73 121 211 1524 5384 528 3846 9254 13b 289 183t 5972 596 321S _?875 145 232 1927 6423 6473975 9936 18? 2S0 1993 7895 968 5423该顺序存储元素为；i師 121 136 145 1B7 206 211 232 276 289 43? 52H 596 64? 9G8 ：10)21 1524 1836 1927 1993 3218 3524 384654 9875 9936|称i快速轴序法务泡排序3975 4523 5210 5384