淺談排序(Sorting algorithm)

維基百科中的資料(http://en.wikipedia.org/wiki/Sorting_algorithm)：

        在計算機科學與數學中，一個排序演算法（Sorting algorithm）是一種能將一串資料依照特定排序方式的一種演算法。

        雖然排序演算法是一個簡單的問題，但是從計算機科學發展以來，已經有大量的研究在此問題上。舉例而言，氣泡排序在1956年就已經被研究。雖然大部分人認為這是一個已經被解決的問題，有用的新演算法仍在不斷的被發明。



        上述內容是從中文版本複製過來的，不過和英文版本還是有些差異，很多資料其實建議看原文，就目前我在查一些資料大概Google都會直接跑出英文的頁面或簡中的，說真的，也網路資訊流通也方便多了，都能直接在網路上查到別人提供的資料或演算法，但是就目前來講我的英文還完全不行，看一頁原文書也能看一小時還看不懂。


        排序演算法維基上就能看到有非常的多，不過我會的不用五根手指頭就能數出來了，所以我頂多只能做幾個介紹而且可能不是很詳細請多多包涵，下列說明都是以排序結果為由小到大來說明。
        
        像大家比較了解的可能就是Bubble sort(氣泡排序)，基本上課程如果有教程式設計的大概會教氣泡排序吧。
        
        Bubble sort的平均複雜度是O(N^2)，作法：
(1)從第一個數開始，比較相鄰數字，如果前面大於後面就將兩數交換。
(2)交換完可最大的數字移到最後方(泡泡浮出？)，最後的部分就視為已排序部分
(3)重複步驟(1)比較未排序部分，依序由大到小在後方浮出，結果即為由小到大排序的結果。


        提供可能看不懂的程式碼：

void bubble_sort(int a[],int n){
    for (int i=0;i<n-1;i++)
        for (int j=0;j<n-i-1;j++)
            if (a[j]>a[j+1])
                swap(a[j],a[j+1]);
}

        初學其他排序演算法的時候我唯一看的懂的是Merge sort(合併排序)，感覺對我來說比較好理解？不過作法上比較耗費記憶體，需要額外O(N)的記憶體空間。
        Merge sort的平均複雜度是O(N logN)，作法：
    (1)把需要排序的部分分成前後兩部分，分別對前後兩部分作合併排序
    (2)再來將前後兩部分作合併，由於前後兩部分皆已做過排序為由小到大，因此每次只需挑選前或後哪一個比較小，依次放到現在正在排序的這部分，這樣就能夠將這部分由小到大排序。

 

        維基百科中介紹Merge sort的圖，意外發現竟然跟章裕老師給的講義上的一樣？

        我是覺得看程式碼或圖會比說明清楚，以下是我的疑似記憶體處理不當的程式碼：

void merge(int l,int mid,int r,int a[]){
    int lnum=mid-l+1,rnum=r-mid,left[lnum+1],righ[rnum+1];
    for (int i=0;i<lnum;i++)
        left[i]=a[l+i];
    for (int i=0;i<rnum;i++)
        righ[i]=a[mid+i+1];
    left[lnum]=righ[rnum]=2147483647;
    int lat=0,rat=0;
    for (int i=0;i<lnum+rnum;i++){
        if (left[lat]<=righ[rat])
            a[l+i]=left[lat++];
        else 
            a[l+i]=righ[rat++];
    }
}
void merge_sort(int l,int r,int a[]){
    if (l==r)
        return;
    int mid=(l+r)/2;
    merge_sort(l,mid,a);
    merge_sort(mid+1,r,a);
    merge(l,mid,r,a);
}

        
        後來複習Merge sort的時候也順便看了Quick sort(快速排序)，從名字上來看看似非常強大，平均複雜度為O(N logN)，不過最差的情況可能到O(N^2)，如果測資故意刁鑽就會大爆炸，不過基本上還是一個很好用的排序法，作法：
    (1)選擇要排序的部份的第一個數當作鍵值，由前往後尋找一個比鍵值大的數，由後往前尋找一個比鍵值小的數字，互相交換，在繼續尋找交換。
    (2)如果由後往前找到的數的位置已經比由前往後找到的數還前面就停止交換，將鍵值與由後往前找到的位置交換。
    (3)步驟(2)完會將目前需要排序的部份分為前後兩部份和鍵值，前面部份的數字皆小於鍵值，後面的部份皆大於鍵值，只要分別在對前後兩部份作快速排序即可。

        維基百科上的Quick sort。

        因為我只寫過一次Quick sort，這一次重寫鍵值交換部份有不少癥結，還好Co出來測試之後沒有Bug：

void quick_sort(int l,int r,int a[]){
    if (l>=r)
        return;
    int k=a[l],low=l+1,high=r;
    while (1){
        while (low<=r&&a[low]<=k) low++;
        while (high>=l+1&&a[high]>k) high--;
        if (low>=high)
            break;
        swap(a[low],a[high]);
    }
    swap(a[l],a[high]);
    quick_sort(l,high-1,a);
    quick_sort(high+1,r,a);
}

        最後一個就Heap sort(堆積排序)，這就要提到另一個資料結構Heap(堆積)，每次查詢最大值(或最小值)只需O(logN)的時間，大概提一下堆積的性質：

        Heap是樹形的資料結構，通常都是用二元樹表示，以Max-heap來說，根節點的值皆大於其左右子樹中任何一個數字的值，而每個子節點也都符合Heap的性質。

        用Heap來做輔助，就能夠做到每次O(logN)找出當前最小值放到陣列中，所需花費的排序時間也就是O(N logN)。

        關於Heap的操作就不多說了，因為初學的時候看不懂，最近才比較常寫到才稍微熟一點，不過，當初真的是看完完全不懂，有興趣的話可以自行找書或Google一下。

        程式碼(備註：以上三種都是將資料存在0~N-1，在這邊是1~N)：

void heap_down(int x,int a[],int num){
    int s=x<<1,v=a[x];
    while (s<=num){
        if (s<num&&a[s+1]>a[s])
            s++;
        if (a[s]<=v)
            break;
        a[x]=a[s],x=s,s<<=1;
    }
    a[x]=v;
}
void heap_sort(int a[],int n){
    for (int i=n>>1;i>=1;i--)
        heap_down(i,a,n);
    for (int i=n;i>=2;i--){
        swap(a[1],a[i]);
        heap_down(1,a,i-1);
    }
}

---------------------------------------------------------------------------------------------------------

        接下來其實才是這整篇的伏筆(阿不是)。

        

        競賽中有很多題目都可能需要排序後才能做某些算法，有些可能光想出作法就要花一堆時間了，但是如果光卡再排序寫不出來或者是需要多花時間去寫排序，這樣起不是划不來？C++中就有提供STL的樣板，裡面就已經包含了幾種Sort，而且也提供了Heap的函式。

        

        如果是要使用排序的話，記得引入函式庫algorithm

#include <algorithm>

        裡面有提供不知道幾種(？)排序，大概比較常用的就是sort和stable_sort，sort中是使用Quick sort，而stable_sort中提供的是Merge_sort。

        用法：

stable_sort(a,a+n);
sort(a,a+n);//排序a[0]~a[n-1]，預設是由小到大

        STL提供的排序還有一個好處就是能夠自訂函式排序，像是如果要由大到小排序的話，只要另外寫一個函式：

bool cmp(int i,int j){
    if (i>j) return true;
    else     return false;
}

        

        然後sort的用法就必須改成這樣：

sort(a,a+n,cmp);

        傳回true的條件會讓左邊的數往前排，如果題目要求很多就只需要在cmp函式多加其他條件就可以了，STL樣板真是超強的，不過sort貌似有時候會出現Runtime error，我是沒去Google過所以不清楚，改用stable_sort就沒問題了。