我最喜欢的排序算法快速排序和归并排序

1、我最喜欢的排序算法快速排序和归并排序我最喜欢的排序算法-快速排序和归并排序2011-02-0520:35摘要：一般评判排序算法的标准有时刻代价，空间代价和稳固性。本文主要讨论性质相对比较好且作者喜欢的快速排序算法和归并排序算法，并对此这做了必然比较。正文：常见的排序算法大致分为四类：1 .插入排序：直接插入排序，Shell排序2 .选择排序：直接选择排序，堆排序3 .互换排序：冒泡排序，快速排序4 .归并排序而对排序算法的一般评判标准有：时刻代价：比较次数、移动次数空间代价：额外空间、堆栈深度稳固性：存在多个具有相同排序码的记录排序后这些记录的相对顺序维持不变下面咱们先用这些评判标准对这些算法

2、做一下大体评价：从那个表中能够看出，快速排序、归并排序和堆排序的时刻代价是比较小的，而其他几个的时刻代价相对比较大。咱们明白时刻复杂度是评判一个算法的最主要标准。程序运行速度直接关系着算法的可行性。而真正美好的算法也一定是运行速度比较快的。但是，由于此刻运算机硬件的进展，尤其是多级缓存的引入，致使堆排序在实际运行中并非快。而且堆排序算法相对比较难理解，程序实现也相对困难，如此的算法显然不是美好的算法。至少在快速排序眼前很难找到优势。而对于快速排序和归并排序，咱们先做一简单介绍，然后别离分析，最后对比分析。快速排序：算法思想：以第一个元素为准，小于该元素的放在左侧，不小于该元素的放在右边，然后对

3、双侧元素递归排序。算法：voidquicksort(intl,intu)inii,m；if(l=u)rcturn；m=l；f()r(i=l+l；i=u；i+)if(xixl)swap(+m,i)；swapQ,m)；quicksort。,m-1)；quicksort(m+l,u)；这里假设x为全局变量。改良：快速排序有一个专门大不足就是对于比较有序的数组排序效率很低，而且当数组较短时快速排序并非是最快的。应对这些情形有三种简单常常利用的改良：随机化改良：不是选取第一个值为基准，而是随机选取。平衡化改良：取第一个、最后一个和中间点三个值中中间值为基准进行排序。设置阀值-混合排序：当数组长度小于某一

4、值时利用其他较快的排序。算法分析：时刻代价：最好情形是。("，唁电最坏情形是。(n2)。若是设f(n)为数组长为n时的比较次数，则f(n)=(f(l)+f(n-1)+(f(2)+f(n-2)+.+(f(n-l)+f(1)/n.利用数学知识易知f(n)=(n+l)*l/2+l/3+.+l/(n+l)-2n-1.386nk)g(n).空间代价：程序所需的空间即为堆栈深度(用于存储5,m),所以空间代价为O(log(n)稳固性：快速排序时不稳固的，即不保序的。评价：快速排序的时刻代价比较低，空间代价也比较低，算是时空代价相当好的算法。而且在下面的数值实验中也会发觉，快速排序效率仍是专门好的

5、。可是最大的不足使快速排序不稳固。比如在CXB1中进行排序，咱们自然希望排序结杲是稳固的(即相同的数排序后与原来的顺序相同)。归并排序：算法思想：将长为的n序列分为长度相当的左右两列，别离排序，然后再归并。即先分后合。算法：voidmcrgc_sort(intl,intu)if(l+1=u)basic_mcrgc_sort(l,u)；return；intc=(l+u)/2；mcrge_sort(l,c)；mcrgc_sort(+c,u)；mcrgc(l,u)；其中basic_ncrgc-sori算法为：voidbasic_mcrgc_sort(intl,intu)if(u-l=l)&&

6、amp;(xlxu)swap(l,u)；其中的merge算法作用是：将两个有序的序列排成一个有序序列，算法如下：voidmcrgc(intl,intu)intc=(l+u)/2,j=c+l,i；ft)r(i=l;i=u；i+)y0=xi;i二i；whilc(l=c&&j=u)if(yPyj)xi+=yD+；elsexi+=yl+；whilc(l=c)xi+=y14-+；while(j=u)xi+=y0+；改良：归并排序使历时大体上利用的和这种似。算法分析：时刻代价：设f(n)为数组长为n时的比较次数，则f(n户f(n/2)+f(n+l)/2)+n.则利用数学知识很容易看出f(n

7、)为。例。虱n)的。空间代价：归并排序所需空间除堆栈深度之外还需要开长度为n的空间。所以归并排序的空间代价为。稳固性：由于归并排序中并无利用出现对换，所以排序时稳固的。评价：归并排序时刻代价是比较理想的，而且算法是稳固的，那个是专门好的。可是不足的是排序的空间代价比较大，需要开一个与原数组一样大小的数组。二种算法对比：时刻代价：从时刻复杂度上看，两个算法平分秋色。但理论分析并非等于实际运行结果。于是我对两种算法用C实现了一下，别离用visualstdi。C+6.0和DevC+编译，在我的COMPAQBl800笔记本(1.73GHz主频)上运行。运行结果如下：(N为数组长度，由于排序算法专门快，

8、且快排运行时刻随机性比较大，我对每一个排序都运行了times次，每次数组元素都是随机选取)visualstdioC+6.0上运行时刻(ms)N和times归并快排N=500timcs=1000()13952593N=1(X)0timcs=1000031655645N=2000timcs=10000697412115N=10000timcs=10()043086986DevC+上最优化编译后运行时刻(ms)N和times归并快排N=500timcs=l00()()591594N=1000timcs=100001515907N=2000iimcs=1000026202381N=10000timcs

9、=100031563172两个编译器的运行时刻很出乎意料，不但DevC+上运行时刻降低了,而且连二者的相对速度都不一样。从VC上来看，显然归并要优于快排，而且又是很明显。而从Dev上来看，结果就不一样了，二者一般情形下运行速度一样，部份情形下快排较好。那个运行结果与网上的一致评论比较相似。对于这种情形我的解释：不同编译器编译原理不同，众所周知，Dev编译的结果一般是明显优于VC编译结果的，这里数据不同的原因部份也就是那个。而不同编译器编译的执行文件里都会有些辅助信息，这些必然程度上降低了程序的运行速度，这也是在VC上二者运行速度相差专门大的原因。再加上此刻电脑各级内存的引入使得程序运行速度的快

10、慢远远不能只从理论分析值上来看。所以两个编译器的运行结果是大大不同的。不过整体来讲，两种排序的运行效率应该是相差无几的。不过若是选用VC编译器的话，归并有必然优势。但如果是选用其他变异效果比较好的编译器，二者效率相差就不明显了。空间代价：正如上面所分析的那样，快排的空间代价为推栈深度，但快排最坏情形堆栈深度为3最好情形为1。虱n),平均情形为。(1。虱n)。归并排序堆栈深度为。(匕虱n),但还需要额外的大小为n的空间，所以空间代价为O(n)o从空间代价上来看，归并排序不如快速排序。稳固性：从上面的分析上明白，快速排序时不稳固的，而归并排序是稳固的。在这方面两个排序完全不同。若是对稳固性没有要求，则二者没有太大差距；但如果是对稳固性有要求,则快速排序则不适用。所以归并排序在这方面有一个比较大的优势。从上面三个方面上看，快速排序的时空代价相对较小，略比归并要好。这应该是大家特别看好快速排序的原因。乃至快排仍是20世纪十大经典算法之一。但归并排序的劣势并非是很明显，而且归并排序的算法思想是如此简单。更重要的是，归并排序是稳固的。这些应该是归并排序能与快速排序对抗的主要原因。这两个排序算法是我最喜欢的。固然若是非要从