羅朝輝（飄飄白云）

排序算法之交換排序   

羅朝輝（http://www.shnenglu.com/kesalin）

轉載請注明出處

排序是數據處理中經常使用的一種重要運算，在計算機及其應用系統中，花費在排序上的時間在系統運行時間中占有很大比重，其重要性無需多言。下文將介紹常用的如下排序方法，對它們進行簡單的分析和比較，并提供 C 語言實現。

所謂排序，就是要將一堆記錄，使之按關鍵字遞增(或遞減)次序排列起來。根據排序所采用的策略，可以分為如下五種：

1、插入排序（直接插入排序、希爾排序）；

2、交換排序（冒泡排序、快速排序）；

3、選擇排序（直接選擇排序、堆排序）；

4、歸并排序；

5、桶排序（桶排序，基數排序）；

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

前面我們講了插入排序，下面接著來講交換排序。

交換排序的基本思想是：兩兩比較待排序記錄的關鍵字，發現兩個記錄的次序相反時即進行交換，直到沒有反序的記錄為止。應用交換排序基本思想的主要排序方法有：冒泡排序和快速排序。

冒泡排序（Bubble Sorting）

基本思想：從后往前掃描序列，通過相鄰元素之間的比較與交換，使值較小的元素逐漸從后部移向前部（從下標較大的單元移向下標較小的單元），就象水底下的氣泡一樣逐漸向上冒。故稱為冒泡排序法。

C 代碼實現：

 1void bubble_sort(int* array, int length)
 2{
 3    assert(array && length >= 0);
 4
 5    int i, j, temp;
 6
 7    for (i = 1; i < length; ++i) {
 8        for (j = length - 1; j >= i; --j) {
 9            if (array[j] < array[j - 1]) {
10                temp = array[j];
11                array[j] = array[j - 1];
12                array[j - 1] = temp;
13            }
14        }
15    }
16}

   若在某一趟排序中未發現氣泡位置的交換，則說明待排序的無序區中所有氣泡均滿足輕者在上，重者在下的原則，因此，冒泡排序過程可在此趟排序后終止。因此，上面的實現可以優化如下：

 1void bubble_sort(int* array, int length)
 2{
 3    assert(array && length >= 0);
 4
 5    int i, j, temp;
 6    bool exchange;
 7
 8    for (i = 1; i < length; ++i) {
 9        exchange = false;
10
11        for (j = length - 1; j >= i; --j) {
12            if (array[j] < array[j - 1]) {
13                temp = array[j];
14                array[j] = array[j - 1];
15                array[j - 1] = temp;
16
17                exchange = true;
18            }
19        }
20
21        if (!exchange) {
22            break;
23        }
24    }
25}

   還可以通過減少排序的趟數作進一步的優化。在每趟掃描中，記住最后一次交換發生的位置 lastExchange （該位置之前的相鄰記錄均已有序）。下一趟排序開始時，array[1..lastExchange - 1] 是有序區， array[lastExchange..n] 是無序區。這樣，一趟排序可能使當前有序區擴充多個記錄，從而減少排序的趟數。實現如下：

 1void bubble_sort(int* array, int length)
 2{
 3    assert(array && length >= 0);
 4
 5    int i, j, temp;
 6    bool exchange;
 7    int lastExchange = 1;
 8
 9    for (i = 1; i < length;) {
10        exchange = false;
11
12        for (j = length - 1; j >= i; --j) {
13            if (array[j] < array[j - 1]) {
14                temp = array[j];
15                array[j] = array[j - 1];
16                array[j - 1] = temp;
17
18                lastExchange = j;
19                exchange = true;
20            }
21        }
22
23        if (!exchange) {
24            break;
25        }
26
27        i = lastExchange + 1;
28    }
29}

   如果待排序序列是基本有序（比如只有第一個元素是最大的，其他的都已有序，在這種情況下，本該只需要 1 趟排序就可以完成），如果用上面的實現 ，這時平均時間復雜達到最壞 O(n^2）。 在這種情況下，可以通過交替改變掃描方向（從后往前，從前往后，再從后往前...）改變不對稱性達到優化的目的。具體實現就留著當作業啦，^_^

時間復雜度：
最好的情況下，待排序記錄已經有序，只需要一趟排序就可以完成，所以冒泡排序的最好時間復雜度為 O(n)。
最壞的情況下，待排序記錄反序，這時需要 n - 1 趟排序，每趟排序需要比較 n - i 次比較操作，這時比較和移動的次數達到最大值，所以冒泡排序的最壞時間復雜度為 O(n ^ 2)。

冒泡排序的平均時間復雜度為 O(n ^ 2)。因為它移動的次數較多，其平均時間性能還不如直接插入排序。

空間復雜度：
很明顯，O(1)。

補充：
冒泡排序是就地排序，且是穩定排序。

快速排序

基本思想：采用分治法。設當前待排序的無序區為 array[low..high]，在其中任選一個記錄作為基準(Pivot)，調整基準在序列中的位置 prvotpos，使左邊子區間中所有記錄的關鍵字均小于等于基準記錄的關鍵字，右邊的子區間中所有記錄的關鍵字均大于等于基準記錄的關鍵字。即基準將當前無序區劃分為左、右兩個較小的子區間 array[low..pivotpos - 1] 和 array[pivotpos + 1..high]，而基準記錄已經處在正確的位置上，它無須參加后續的排序。這時，排序問題就分解成兩個子區間的排序問題（這就是分而治之的思想啊）， 遞歸對左右子區間進行快速排序，就可以完成排序。

BTW，分治法的基本思想：將原問題分解為若干個規模更小但結構與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。

代碼實現：

 1// 對 [low, high] 做劃分，并返回基準記錄的位置
 2int quick_partition(int* array, int low, int high)
 3{
 4    assert(array && low >= 0 && low <= high);
 5
 6    int pivot = array[low]; // 用區間的第 1 個記錄作為基準
 7
 8    while (low < high) {
 9        while (low < high && array[high] >= pivot) {
10            --high;
11        }
12
13        if (low < high) {
14            array[low++] = array[high];
15        }
16
17        while (low < high && array[low] <= pivot) {
18            ++low;
19        }
20
21        if (low < high) {
22            array[high--] = array[low];
23        }
24    }
25
26    array[low] = pivot;
27
28    return low;
29}
30
31void quick_sort_impl(int* array, int low, int high)
32{
33    if (low < high) {
34        int pivotPos = quick_partition(array, low, high);
35
36        quick_sort_impl(array, low, pivotPos - 1);
37        quick_sort_impl(array, pivotPos + 1, high);
38    }
39}
40
41// 快速排序
42//
43void quick_sort(int* array, int length)
44{
45    assert(array && length >= 0);
46
47    if (length <= 1) {
48        return;
49    }
50
51    quick_sort_impl( array, 0, length - 1);
52}

時間復雜度分析：
最壞情況是每次劃分選取的基準都是當前無序區中關鍵字最小(或最大)的記錄，劃分的結果是基準左邊的子區間為空(或右邊的子區間為空)，而劃分所得的另一個非空的子區間中記錄數目，僅僅比劃分前的無序區中記錄個數減少一個。此時，時間復雜度為 O(n ^ 2)。

在最好情況下，每次劃分所取的基準都是當前無序區的"中值"記錄，劃分的結果是基準的左、右兩個無序子區間的長度大致相等。總的關鍵字比較次數：0(nlgn)。

盡管快速排序的最壞時間為 O(n ^ 2)，但就平均性能而言，它是基于關鍵字比較的內部排序算法中速度最快者，快速排序亦因此而得名。它的平均時間復雜度為 O(nlgn)。

空間復雜度分析：
快速排序需要一個棧來實現遞歸。若每次劃分較為均勻（也就是對半分，基準值總是中值），則其遞歸樹的高度為O(lgn)，故遞歸后需棧空間為O(lgn)。最壞情況下，遞歸樹的高度為O(n)，所需的棧空間為O(n)。

補充：
快速排序是非穩定的。例如，對 [5, 5, 1] 進行排序。

對時間復雜度進行分析之后，可以看出，在當前無序區中選取劃分的基準關鍵字是決定算法性能的關鍵。可以對這個進行一定程度的優化：
第一辦法是，取中值，即比較當前無序區間的第一個，中間那個以及最后一個記錄的大小，取中間的那個記錄作為基準，進行快速排序；
第二個辦法是，在當前無需區間中進行隨機選取。

測試：
在前文《排序算法之插入排序》測試代碼的基礎上添加兩行代碼即可：