排序算法的时间性能比较

1、排序算法时间性能比较一、问题说明提供一系列实验，比较排序算法快速排序、堆排序、冒泡排序等时间性能二、基本要求(1)时间性能包括平均时间性能、最佳时间性能和最差时间性能。(2)实验数据要大(例如100 10000)，并且要有说服力，包括因为数据的初始特性类型很多，所以要有随机性。实验数据的组数更多。换句话说，大小相同的数组需要选择多个茄子不同类型的数据并进行实验。实验结果必须能以图画、表格等明确的形式提出。(3)算法时间必须是机器时间，也可以包括元素比较和更换次数。(4)实验分析及其结果应能以数学公式、图表等明确的方式说明。(5)应提供实验方案和分析。三、工具/准备工作Microsoft Vis

2、ual C 6.0软件。四、分析与实现1.快速选择排序这是冒泡排序的改善。他的基本思想现在是无序的区域R1。H采取某种数据元素基准，将当前无序的区域分为左右两个较小的无序区域。r1.I-1和RI 1.H，直到对所有未排序子区域的数据元素进行了排序。2.排序堆堆排序本质上是具有以下特性的完整二叉树：树中所有非叶节点的关键字大于子节点等关键字。这只需要记录大小辅助空间。要排序的每个记录只占用一个存储空间，普通唱片的数量很小。但是基数大的文件仍然有效。因为运行时间主要是在制作初始堆和调整新堆时重复进行的过滤。3.冒泡排序牙齿排序的比较基本思想是22要排序的数据元素大小比较，发现两个数据元素顺序相反的

3、时候交换，可以看出没有相反的数据。(阿尔伯特爱因斯坦、Northern Exposure(美国电视电视剧)、Northern Exposure冒泡排序一次比较最小或最大值，然后将其放在序列中的最后一个位置，然后从一个位置重复N-1的剩馀操作。排序算法时间空间复杂性排序方法最坏的情况平均情况最佳情况快速排序O(nlogn)O(n2)O(1)排序堆O(nlogn)O(nlogn)O(n)冒泡排序O(n2)O(nlogn)O(n)节目代码：#include#include#include#define MAXSIZE 50Typedef int KeyType#define MAXNUM 100Ty

4、pedef structKeyType Key RedTypeRedType Rmax num；Typedef structRedType rMAXSIZE 1；Int lengthSqlistSqlist l、l0、L1、L2、L3、l4、l5、l6、l7；Typedef Sqlist HeadType#define RADIX 10#define MAX 8#define MAX_SPACE 10000Typedef int KeysTypeTypedef struct密钥类型密钥最大；Int nextSLCellTypedef struct sl cell rlMAX _ SPACE；I

5、nt KeynumInt recnumSl列表；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.lengthI) scanf(“% d”，l . rI)；Void shuChu(Sqlist L)int I=1；Printf(“牙齿序列存储中的数据元素：”)；for(；I=pivotKey)-高度；compare4；l . rl

6、ow=l . rhigh；变更4；compare4；While (lowH.rj)。Key) compare5；布列克；h . rs=h . rj；s=j；变更5；h . rs=RC；变更5；Void headsort(头部类型h) RedType tempfor(int I=h . length/2；i0；-I) compare5；HeadAdjust (H，I，H . length)；for(I=h . length)；i1；I -) compare5；temp=h . r1；h . r1=h . rI；h . rI=temp；变更5=3HeadAjust (H，1，I-1)；/=气泡对齐

7、=Void bubbleSort (Sqlist L)int i，j，tempFor(i=1，i=L.lengthI) compare2；compare2；if(l . rj. keyl .j 1. key 0；L.rj=1。Key=tempCharge2=3Printf(t选择要执行的操作。 t n )；Printf(tcase 1:在排序之前生成完全随机的数据。 t n )；printf(“ tcase 23360自行输入部分数据后执行排序操作 t n”)；printf(“ tcase 03360退出节目 t n”)；Void TablePrintf(t=算法名称=比较计数=更换计数=pr

8、intf(“ t1快速排序t% d t% d t n”，comparehchange5)；Printf(t=算法名称=比较计数=更换计数=printf(“ t1堆排序t% d t% d t n”，comparehchange3)；Printf(t=算法名称=比较计数=更换计数=printf(“ t1冒泡排序t% d t% d t n”，comparehchange0)；Void随机(sqlist L) SLList LKfor(int I=0)；i8；I)comparei=0变更I=0Printf(输入生成的随机数数据计数： )Printf(“”排序前随机数的%d计数为：n，l . lengt

9、h)；for(I=1)；I=l.length3360i)printf(“% d”，L.ri)。key)；Printf(n下面执行的每个排序的操作，您的)；Void mian()Int choosemen()；Printf(选择“ t:”)；Scanf(选择)case 13360 random(L)；Break:case 23360 yonghu(L)；Break:Case : nixh (l) : Break:case 0；Return五、测试和结论输入数据后，结果如下：1需要随机生成12个数字的结果如下：但是随机生成的34个数字的结果是：结论：从数据结果中可以看出，排序的数据较少时快速排序数最快，大数据时堆排序是更好的选择。(David aser，Nor