我最喜歡的排序算法快速排序和歸并排序

1、我最喜歡的排序算法快速排序和歸并排序我最喜歡的排序算法-快速排序和歸并排序2011-02-0520:35摘要：一般評判排序算法的標(biāo)準(zhǔn)有時刻代價，空間代價和穩(wěn)固性。本文主要討論性質(zhì)相對比較好且作者喜歡的快速排序算法和歸并排序算法，并對此這做了必然比較。正文：常見的排序算法大致分為四類：1 .插入排序：直接插入排序，Shell排序2 .選擇排序：直接選擇排序，堆排序3 .互換排序：冒泡排序，快速排序4 .歸并排序而對排序算法的一般評判標(biāo)準(zhǔn)有：時刻代價：比較次數(shù)、移動次數(shù)空間代價：額外空間、堆棧深度穩(wěn)固性：存在多個具有相同排序碼的記錄排序后這些記錄的相對順序維持不變下面咱們先用這些評判標(biāo)準(zhǔn)對這些算法

2、做一下大體評價：從那個表中能夠看出，快速排序、歸并排序和堆排序的時刻代價是比較小的，而其他幾個的時刻代價相對比較大。咱們明白時刻復(fù)雜度是評判一個算法的最主要標(biāo)準(zhǔn)。程序運(yùn)行速度直接關(guān)系著算法的可行性。而真正美好的算法也一定是運(yùn)行速度比較快的。但是，由于此刻運(yùn)算機(jī)硬件的進(jìn)展，尤其是多級緩存的引入，致使堆排序在實(shí)際運(yùn)行中并非快。而且堆排序算法相對比較難理解，程序?qū)崿F(xiàn)也相對困難，如此的算法顯然不是美好的算法。至少在快速排序眼前很難找到優(yōu)勢。而對于快速排序和歸并排序，咱們先做一簡單介紹，然后別離分析，最后對比分析?？焖倥判颍核惴ㄋ枷耄阂缘谝粋€元素為準(zhǔn)，小于該元素的放在左側(cè)，不小于該元素的放在右邊，然后對

3、雙側(cè)元素遞歸排序。算法：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)；這里假設(shè)x為全局變量。改良：快速排序有一個專門大不足就是對于比較有序的數(shù)組排序效率很低，而且當(dāng)數(shù)組較短時快速排序并非是最快的。應(yīng)對這些情形有三種簡單常常利用的改良：隨機(jī)化改良：不是選取第一個值為基準(zhǔn)，而是隨機(jī)選取。平衡化改良：取第一個、最后一個和中間點(diǎn)三個值中中間值為基準(zhǔn)進(jìn)行排序。設(shè)置閥值-混合排序：當(dāng)數(shù)組長度小于某一

4、值時利用其他較快的排序。算法分析：時刻代價：最好情形是。("，唁電最壞情形是。(n2)。若是設(shè)f(n)為數(shù)組長為n時的比較次數(shù)，則f(n)=(f(l)+f(n-1)+(f(2)+f(n-2)+.+(f(n-l)+f(1)/n.利用數(shù)學(xué)知識易知f(n)=(n+l)*l/2+l/3+.+l/(n+l)-2n-1.386nk)g(n).空間代價：程序所需的空間即為堆棧深度(用于存儲5,m),所以空間代價為O(log(n)穩(wěn)固性：快速排序時不穩(wěn)固的，即不保序的。評價：快速排序的時刻代價比較低，空間代價也比較低，算是時空代價相當(dāng)好的算法。而且在下面的數(shù)值實(shí)驗(yàn)中也會發(fā)覺，快速排序效率仍是專門好的

5、。可是最大的不足使快速排序不穩(wěn)固。比如在CXB1中進(jìn)行排序，咱們自然希望排序結(jié)杲是穩(wěn)固的(即相同的數(shù)排序后與原來的順序相同)。歸并排序：算法思想：將長為的n序列分為長度相當(dāng)?shù)淖笥覂闪?，別離排序，然后再歸并。即先分后合。算法：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+；改良：歸并排序使歷時大體上利用的和這種似。算法分析：時刻代價：設(shè)f(n)為數(shù)組長為n時的比較次數(shù)，則f(n戶f(n/2)+f(n+l)/2)+n.則利用數(shù)學(xué)知識很容易看出f(n

7、)為。例。虱n)的?？臻g代價：歸并排序所需空間除堆棧深度之外還需要開長度為n的空間。所以歸并排序的空間代價為。穩(wěn)固性：由于歸并排序中并無利用出現(xiàn)對換，所以排序時穩(wěn)固的。評價：歸并排序時刻代價是比較理想的，而且算法是穩(wěn)固的，那個是專門好的?？墒遣蛔愕氖桥判虻目臻g代價比較大，需要開一個與原數(shù)組一樣大小的數(shù)組。二種算法對比：時刻代價：從時刻復(fù)雜度上看，兩個算法平分秋色。但理論分析并非等于實(shí)際運(yùn)行結(jié)果。于是我對兩種算法用C實(shí)現(xiàn)了一下，別離用visualstdi。C+6.0和DevC+編譯，在我的COMPAQBl800筆記本(1.73GHz主頻)上運(yùn)行。運(yùn)行結(jié)果如下：(N為數(shù)組長度，由于排序算法專門快，

8、且快排運(yùn)行時刻隨機(jī)性比較大，我對每一個排序都運(yùn)行了times次，每次數(shù)組元素都是隨機(jī)選取)visualstdioC+6.0上運(yùn)行時刻(ms)N和times歸并快排N=500timcs=1000()13952593N=1(X)0timcs=1000031655645N=2000timcs=10000697412115N=10000timcs=10()043086986DevC+上最優(yōu)化編譯后運(yùn)行時刻(ms)N和times歸并快排N=500timcs=l00()()591594N=1000timcs=100001515907N=2000iimcs=1000026202381N=10000timcs

9、=100031563172兩個編譯器的運(yùn)行時刻很出乎意料，不但DevC+上運(yùn)行時刻降低了,而且連二者的相對速度都不一樣。從VC上來看，顯然歸并要優(yōu)于快排，而且又是很明顯。而從Dev上來看，結(jié)果就不一樣了，二者一般情形下運(yùn)行速度一樣，部份情形下快排較好。那個運(yùn)行結(jié)果與網(wǎng)上的一致評論比較相似。對于這種情形我的解釋：不同編譯器編譯原理不同，眾所周知，Dev編譯的結(jié)果一般是明顯優(yōu)于VC編譯結(jié)果的，這里數(shù)據(jù)不同的原因部份也就是那個。而不同編譯器編譯的執(zhí)行文件里都會有些輔助信息，這些必然程度上降低了程序的運(yùn)行速度，這也是在VC上二者運(yùn)行速度相差專門大的原因。再加上此刻電腦各級內(nèi)存的引入使得程序運(yùn)行速度的快

10、慢遠(yuǎn)遠(yuǎn)不能只從理論分析值上來看。所以兩個編譯器的運(yùn)行結(jié)果是大大不同的。不過整體來講，兩種排序的運(yùn)行效率應(yīng)該是相差無幾的。不過若是選用VC編譯器的話，歸并有必然優(yōu)勢。但如果是選用其他變異效果比較好的編譯器，二者效率相差就不明顯了?？臻g代價：正如上面所分析的那樣，快排的空間代價為推棧深度，但快排最壞情形堆棧深度為3最好情形為1。虱n),平均情形為。(1。虱n)。歸并排序堆棧深度為。(匕虱n),但還需要額外的大小為n的空間，所以空間代價為O(n)o從空間代價上來看，歸并排序不如快速排序。穩(wěn)固性：從上面的分析上明白，快速排序時不穩(wěn)固的，而歸并排序是穩(wěn)固的。在這方面兩個排序完全不同。若是對穩(wěn)固性沒有要求，則二者沒有太大差距；但如果是對穩(wěn)固性有要求,則快速排序則不適用。所以歸并排序在這方面有一個比較大的優(yōu)勢。從上面三個方面上看，快速排序的時空代價相對較小，略比歸并要好。這應(yīng)該是大家特別看好快速排序的原因。乃至快排仍是20世紀(jì)十大經(jīng)典算法之一。但歸并排序的劣勢并非是很明顯，而且歸并排序的算法思想是如此簡單。更重要的是，歸并排序是穩(wěn)固的。這些應(yīng)該是歸并排序能與快速排序?qū)沟闹饕颉＿@兩個排序算法是我最喜歡的。固然若是非要從