快速排序和歸并排序

摘要：一般評判排序算法的标準有時間代價，空間代價和穩定性。本文主要讨論性質相對比較好且作者喜歡的快速排序算法和歸并排序算法，并對此這做了一定比較。

正文：

常見的排序算法大緻分為四類：

1.插入排序：直接插入排序，Shell排序

2.選擇排序：直接選擇排序，堆排序

3.交換排序：冒泡排序，快速排序

4.歸并排序

而對排序算法的一般評判标準有：

              時間代價：比較次數、移動次數

              空間代價：額外空間、堆棧深度

              穩定性：存在多個具有相同排序碼的記錄排序後這些記錄的相對次序保持不變

下面我們先用這些評判标準對這些算法做一下基本評價：

從這個表中可以看出，快速排序、歸并排序和堆排序的時間代價是比較小的，而其他幾個的時間代價相對比較大。我們知道時間複雜度是評判一個算法的最主要标準。程式運作速度直接關系着算法的可行性。而真正美妙的算法也必定是運作速度比較快的。然而，由于現在計算機硬體的發展，尤其是多級緩存的引入，導緻堆排序在實際運作中并不快。而且堆排序算法相對比較難了解，程式實作也相對困難，這樣的算法顯然不是美妙的算法。至少在快速排序面前很難找到優勢。

而對于快速排序和歸并排序，我們先做一簡單介紹，然後分别分析，最後對比分析。

快速排序：

算法思想：以第一個元素為準，小于該元素的放在左邊，不小于該元素的放在右邊，然後對兩側元素遞歸排序。

算法：

void quicksort(int l, int u)

{   int i, m;

    if (l >= u) return;

    m = l;

    for (i = l+1; i <= u; i++)

        if (x[i] < x[l])

            swap(++m, i);

    swap(l, m);

    quicksort(l, m-1);

    quicksort(m+1, u);

}

這裡假設x為全局變量。

改進：快速排序有一個很大不足就是對于比較有序的數組排序效率很低，而且當數組較短時快速排序并不是最快的。應對這些情況有三種簡單常用的改進：

随機化改進：不是選取第一個值為基準，而是随機選取。

平衡化改進：取第一個、最後一個和中間點三個值中中間值為基準進行排序。

設定閥值--混合排序：當數組長度小于某一值時使用其他較快的排序。

算法分析：

時間代價：最好情況是O(n log n),最壞情況是O(n2)。如果設f(n)為數組長為n時的比較次數，則f(n)=[(f(1)+f(n-1))+(f(2)+f(n-2))+...+(f(n-1)+f(1))]/n.

利用數學知識易知f(n)=(n+1)*[1/2+1/3+...+1/(n+1)]-2n~1.386nlog(n).

空間代價：程式所需的空間即為堆棧深度(用于存儲l,u,m)，是以空間代價為O(log(n))

穩定性：快速排序時不穩定的，即不保序的。

評價：快速排序的時間代價比較低，空間代價也比較低，算是時空代價相當好的算法。而且在下面的數值試驗中也會發現，快速排序效率還是很好的。但是最大的不足使快速排序不穩定。比如在excel中進行排序，我們自然希望排序結果是穩定的（即相同的數排序後與原來的順序相同）。

歸并排序：

算法思想：将長為的n序列分為長度相當的左右兩列，分别排序，然後再合并。即先分後合。

void merge_sort(int l,int u)

{

if(l+1>=u){basic_merge_sort(l,u);return;}

int c=(l+u)/2;

merge_sort(l,c);

merge_sort(++c,u);

merge(l,u);

其中basic_nerge_sort算法為：

void basic_merge_sort(int l,int u)

if((u-l==1)&&(x[l]>x[u]))

   swap(l,u);

其中的merge算法作用是：将兩個有序的序列排成一個有序序列，算法如下：

void merge(int l,int u)

int c=(l+u)/2,j=c+1,i;

for(i=l;i<=u;i++)

   y[i]=x[i];

i=l;

while(l<=c&&j<=u)

   if(y[l]>y[j]) x[i++]=y[j++];

   else x[i++]=y[l++];

while(l<=c) x[i++]=y[l++];

while(j<=u) x[i++]=y[j++];

改進：歸并排序使用時基本上使用的和這類似。

時間代價：設f(n)為數組長為n時的比較次數，則f(n)=f(n/2)+f((n+1)/2)+n.則利用數學知識很容易看出f(n)為O(nlog(n))的。

空間代價：歸并排序所需空間除了堆棧深度以外還需要開長度為n的空間。是以歸并排序的空間代價為O(n)。

穩定性：由于歸并排序中并沒有使用出現對換，是以排序時穩定的。

評價：歸并排序時間代價是比較理想的，而且算法是穩定的，這個是很好的。但是不足的是排序的空間代價比較大，需要開一個與原數組同樣大小的數組。

二種算法對比：

時間代價：從時間複雜度上看，兩個算法平分秋色。但理論分析并不等于實際運作結果。于是我對兩種算法用C實作了一下，分别用visual stdio C++6.0和Dev C++編譯，在我的COMPAQ B1800筆記本（1.73GHz主頻）上運作。運作結果如下：（N為數組長度，由于排序算法很快，且快排運作時間随機性比較大，我對每個排序都運作了times次，每次數組元素都是随機選取）

visual stdio C++6.0上運作時間（ms）

N和times                   歸并 快排

N=500 times=10000 1395 2593

N=1000 times=10000 3165 5645

N=2000 times=10000 6974 12115

N=10000 times=1000 4308 6986

Dev C++上最優化編譯後運作時間（ms）

N和times                  歸并 快排

N=500 times=10000 591 594

N=1000 times=10000 1515 907

N=2000 times=10000 2620 2381

N=10000 times=1000 3156 3172

兩個編譯器的運作時間很出乎意料，不光Dev C++上運作時間降低了，而且連兩者的相對速度都不一樣。從VC上來看，顯然歸并要優于快排，而且又是很明顯。而從Dev上來看，結果就不一樣了，兩者一般情況下運作速度一樣，部分情況下快排較好。這個運作結果與網上的一緻評論比較相似。

對于這種情況我的解釋：不同編譯器編譯原理不同，衆所周知，Dev編譯的結果一般是明顯優于VC編譯結果的，這裡資料不同的原因部分也就是這個。而不同編譯器編譯的執行文

件裡都會有些輔助資訊，這些一定程度上降低了程式的運作速度，這也是在VC上兩者運作速度相差很大的原因。再加上現在電腦各級記憶體的引入使得程式運作速度的快慢遠遠不能

隻從理論分析值上來看。是以兩個編譯器的運作結果是大大不同的。

不過總體來說，兩種排序的運作效率應該是相差無幾的。不過如果選用VC編譯器的話，歸并有一定優勢。但如果選用其他變異效果比較好的編譯器，兩者效率相差就不明顯了。

空間代價：正如上面所分析的那樣，快排的空間代價為堆棧深度，但快排最壞情況堆棧深度為n，最好情況為log(n)，平均情況為O(log(n))。

歸并排序堆棧深度為O(log(n)),但還需要額外的大小為n的空間，是以空間代價為O(n)。

從空間代價上來看，歸并排序不如快速排序。

穩定性：從上面的分析上知道，快速排序時不穩定的，而歸并排序是穩定的。在這方面兩個排序完全不同。如果對穩定性沒有要求，則兩者沒有太大差距；但如果對穩定性有要求

，則快速排序則不适用。是以歸并排序在這方面有一個比較大的優勢。

從上面三個方面上看，快速排序的時空代價相對較小，略比歸并要好。這應該是大家特别看好快速排序的原因。甚至快排還是20世紀十大經典算法之一。但歸并排序的劣勢并不是很明顯，而且歸并排序的算法思想是如此簡單。更重要的是，歸并排序是穩定的。這些應該是歸并排序能與快速排序抗衡的主要原因。

這兩個排序算法是我最喜歡的。當然如果非要從兩者之間選一個最最喜歡的話，我會選擇歸并排序。一方面在我完全不知道歸并排序的情況下，自己獨立寫出了它的算法并上機實

現了。另一方面，歸并排序思想簡單，是穩定的，适用性優于快速排序。由于其穩定性，我可以大膽的copy這些代碼到我需要用它的地方。