排序

排序

本章先簡單介紹了插入排序，然后著重講述快速排序。

插入排序

// 版本1
void InsertSort(int a[], int n) {
    for(int i=1; i<n; ++i)
        for(int j=i; j>0 && a[j-1]>a[j]; --j)
            swap(a[j-1], a[j]);
}
// 版本2
void InsertSort1(int a[], int n) {
    for(int i=1; i<n; ++i) {
        int t = a[i];
        int j = i;
        for(; j>0 && a[j-1]>t; --j)
            a[j] = a[j-1];
        a[j] = t;
    }
}

快速排序

我們?cè)谶@里規(guī)定：小于等于pivot的元素移到左邊，大于pivot的元素移到右邊。

實(shí)現(xiàn)1：單向移動(dòng)版本

這個(gè)版本的關(guān)鍵是設(shè)置一快一慢兩個(gè)指針，慢指針左側(cè)都是小于等于pivot(包含慢指針?biāo)谖恢?， 慢指針到快指針之間的值是大于pivot，快指針右側(cè)的值是還未比較過的。示意圖如下：

小于等于pivot    ｜    大于pivot    ｜    ？
             slow                fast

快指針一次一步向前走，遇到大于pivot什么也不做繼續(xù)向前走。遇到小于等于pivot的元素， 則慢指針slow向前走一步，然后交換快慢指針指向的元素。一次劃分結(jié)束后， 再遞歸對(duì)左右兩側(cè)的元素進(jìn)行快排。代碼如下：

// 數(shù)組快排
void QSort(int a[], int head, int end) {
    if(a==NULL || head==end) return;
    int slow = head, fast = head + 1;
    int pivot = a[head];
    while(fast != end) {
        if(a[fast] <= pivot)
            swap(a[++slow], a[fast]);
        ++fast;
    }
    swap(a[head], a[slow]);
    QSort(a, head, slow);
    QSort(a, slow+1, end);
}

排序數(shù)組a只需要調(diào)用QSort(a, 0, n)即可。該思路同樣可以很容易地在鏈表上實(shí)現(xiàn)：

// 單鏈表快排
void qsort(Node *head, Node *end){
    if(head==NULL || head==end) return;
    Node *slow = head, *fast = head->next;
    int pivot = head->data;
    while(fast != end){
        if(fast->data <= pivot){
            slow = slow->next;
            swap(slow->data, fast->data);
        }
        fast = fast->next;
    }
    swap(head->data, slow->data);
    qsort(head, slow);
    qsort(slow->next, end);
}

排序頭指針為head的單鏈表只需調(diào)用qsort(head, NULL)即可。

實(shí)現(xiàn)2：雙向移動(dòng)版本

版本1能能夠快速完成對(duì)隨機(jī)整數(shù)數(shù)組的排序，但如果數(shù)組有序， 或是數(shù)組中元素相同，快排的時(shí)間復(fù)雜度會(huì)退化成O(n2?)，性能變得非常差。

一種緩解方案是使用雙向移動(dòng)版本的快排，它每次劃分也是使用兩個(gè)指針， 不過一個(gè)是從左向右移動(dòng)，一個(gè)是從右向左移動(dòng)，示意圖如下：

小于等于pivot    ｜    ？    ｜    大于pivot
               i            j

指針j不斷向左移動(dòng)，直到遇到小于等于pivot，就交換指針i和j所指元素 (指針i一開始指向pivot)；指針i不斷向右移動(dòng)，直到遇到大于pivot的， 就交換指針i和j所指元素。pivot在這個(gè)過程中，不斷地?fù)Q來換去， 最終會(huì)停在分界線上，分界線左邊都是小于等于它的元素，右邊都是大于它的元素。 這樣就避免了最后還要交換一次pivot的操作，代碼也變得美觀許多。

int partition(int a[], int low, int high){
    int pivot = a[low], i=low, j=high;
    while(i < j){
        while(i<j && a[j]>pivot) --j;
        if(i < j) swap(a[i], a[j]);
        while(i<j && a[i]<=pivot) ++i;
        if(i < j) swap(a[i], a[j]);
    }
    return i;
}
void quicksort(int a[], int first, int last){
    if(first<last){
        int k = partition(a, first, last);
        quicksort(a, first, k-1);
        quicksort(a, k+1, last);
    }
}

當(dāng)然，如果對(duì)于partition函數(shù)，你如果覺得大循環(huán)內(nèi)的兩個(gè)swap還是做了些無用功的話， 也可以把pivot的賦值放到最后一步，而不是在這個(gè)過程中swap來swap去的。代碼如下：

int partition(int a[], int low, int high){
    int pivot = a[low], i=low, j=high;
    while(i<j){
        while(i<j && a[j]>pivot) --j;
        if(i<j) a[i++] = a[j];
        while(i<j && a[i]<=pivot) ++i;
        if(i<j) a[j--] = a[i];
    }
    a[i] = pivot;
    return i;
}

如果數(shù)組基本有序，那隨機(jī)選擇pivot(而不像上面那樣選擇第一個(gè)做為pivot) 會(huì)得到更好的性能。在partition函數(shù)里，我們只需要在數(shù)組中隨機(jī)選一個(gè)元素， 然后將它和數(shù)組中第一個(gè)元素交換，后面的劃分代碼無需改變， 就可以達(dá)到隨機(jī)選擇pivot的效果。

進(jìn)一步優(yōu)化

對(duì)于小數(shù)組，用插入排序之類的簡單方法來排序反而會(huì)更快，因此在快排中， 當(dāng)數(shù)組長度小于某個(gè)值時(shí)，我們就什么也不做。對(duì)應(yīng)到代碼中， 就是修改quicksort中的if條件：

if(first < last)  改為  if(last-first > cutoff)

其中cutoff是一個(gè)小整數(shù)。程序結(jié)束時(shí)，數(shù)組并不是有序的， 而是被組合成一塊一塊隨機(jī)排列的值，并且滿足這樣的條件： 某一塊中的元素小于它右邊任何塊中的元素。我們必須通過另一種排序算法對(duì)塊內(nèi)進(jìn)行排序。 由于數(shù)組是幾乎有序的，因此插入排序比較適用。

這種方法結(jié)合了快排和插入排序，讓它們?nèi)プ龈髯陨瞄L的事情，往往比單純用快排要快。

深入閱讀：Don Knuth的《The Art of Computer Programming, Volume 3: Sorting and Searching》；Robert Sedgewick的《Algorithms》； 《Algorithms in C》,《Algorithms in C++》,《Algorithms in Java》。