排序算法之交換排序   

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

轉(zhuǎn)載請(qǐng)注明出處

排序是數(shù)據(jù)處理中經(jīng)常使用的一種重要運(yùn)算，在計(jì)算機(jī)及其應(yīng)用系統(tǒng)中，花費(fèi)在排序上的時(shí)間在系統(tǒng)運(yùn)行時(shí)間中占有很大比重，其重要性無(wú)需多言。下文將介紹常用的如下排序方法，對(duì)它們進(jìn)行簡(jiǎn)單的分析和比較，并提供 C 語(yǔ)言實(shí)現(xiàn)。

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

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

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

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

4、歸并排序；

5、桶排序（桶排序，基數(shù)排序）；

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

前面我們講了插入排序，下面接著來(lái)講交換排序。

交換排序的基本思想是：兩兩比較待排序記錄的關(guān)鍵字，發(fā)現(xiàn)兩個(gè)記錄的次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序的記錄為止。應(yīng)用交換排序基本思想的主要排序方法有：冒泡排序和快速排序。

冒泡排序（Bubble Sorting）

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

C 代碼實(shí)現(xiàn)：

 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}

   若在某一趟排序中未發(fā)現(xiàn)氣泡位置的交換，則說(shuō)明待排序的無(wú)序區(qū)中所有氣泡均滿足輕者在上，重者在下的原則，因此，冒泡排序過(guò)程可在此趟排序后終止。因此，上面的實(shí)現(xiàn)可以優(yōu)化如下：

 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}

   還可以通過(guò)減少排序的趟數(shù)作進(jìn)一步的優(yōu)化。在每趟掃描中，記住最后一次交換發(fā)生的位置 lastExchange （該位置之前的相鄰記錄均已有序）。下一趟排序開(kāi)始時(shí)，array[1..lastExchange - 1] 是有序區(qū)， array[lastExchange..n] 是無(wú)序區(qū)。這樣，一趟排序可能使當(dāng)前有序區(qū)擴(kuò)充多個(gè)記錄，從而減少排序的趟數(shù)。實(shí)現(xià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}

   如果待排序序列是基本有序（比如只有第一個(gè)元素是最大的，其他的都已有序，在這種情況下，本該只需要 1 趟排序就可以完成），如果用上面的實(shí)現(xiàn) ，這時(shí)平均時(shí)間復(fù)雜達(dá)到最壞 O(n^2）。 在這種情況下，可以通過(guò)交替改變掃描方向（從后往前，從前往后，再?gòu)暮笸?..）改變不對(duì)稱性達(dá)到優(yōu)化的目的。具體實(shí)現(xiàn)就留著當(dāng)作業(yè)啦，^_^

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

冒泡排序的平均時(shí)間復(fù)雜度為 O(n ^ 2)。因?yàn)樗苿?dòng)的次數(shù)較多，其平均時(shí)間性能還不如直接插入排序。

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

補(bǔ)充：
冒泡排序是就地排序，且是穩(wěn)定排序。

快速排序

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

BTW，分治法的基本思想：將原問(wèn)題分解為若干個(gè)規(guī)模更小但結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題。遞歸地解這些子問(wèn)題，然后將這些子問(wèn)題的解組合為原問(wèn)題的解。

代碼實(shí)現(xiàn)：

 1// 對(duì) [low, high] 做劃分，并返回基準(zhǔn)記錄的位置
 2int quick_partition(int* array, int low, int high)
 3{
 4    assert(array && low >= 0 && low <= high);
 5
 6    int pivot = array[low]; // 用區(qū)間的第 1 個(gè)記錄作為基準(zhǔn)
 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}

時(shí)間復(fù)雜度分析：
最壞情況是每次劃分選取的基準(zhǔn)都是當(dāng)前無(wú)序區(qū)中關(guān)鍵字最小(或最大)的記錄，劃分的結(jié)果是基準(zhǔn)左邊的子區(qū)間為空(或右邊的子區(qū)間為空)，而劃分所得的另一個(gè)非空的子區(qū)間中記錄數(shù)目，僅僅比劃分前的無(wú)序區(qū)中記錄個(gè)數(shù)減少一個(gè)。此時(shí)，時(shí)間復(fù)雜度為 O(n ^ 2)。

在最好情況下，每次劃分所取的基準(zhǔn)都是當(dāng)前無(wú)序區(qū)的"中值"記錄，劃分的結(jié)果是基準(zhǔn)的左、右兩個(gè)無(wú)序子區(qū)間的長(zhǎng)度大致相等。總的關(guān)鍵字比較次數(shù)：0(nlgn)。

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

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

補(bǔ)充：
快速排序是非穩(wěn)定的。例如，對(duì) [5, 5, 1] 進(jìn)行排序。

對(duì)時(shí)間復(fù)雜度進(jìn)行分析之后，可以看出，在當(dāng)前無(wú)序區(qū)中選取劃分的基準(zhǔn)關(guān)鍵字是決定算法性能的關(guān)鍵。可以對(duì)這個(gè)進(jìn)行一定程度的優(yōu)化：
第一辦法是，取中值，即比較當(dāng)前無(wú)序區(qū)間的第一個(gè)，中間那個(gè)以及最后一個(gè)記錄的大小，取中間的那個(gè)記錄作為基準(zhǔn)，進(jìn)行快速排序；
第二個(gè)辦法是，在當(dāng)前無(wú)需區(qū)間中進(jìn)行隨機(jī)選取。

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