在打鋪克牌時，你會怎麼整理？有人會先找出最小的那張放到最左邊，再從剩下的牌裡找最小的；有人會從左到右一張一張看，把每張牌插進左手邊已經排好的牌之間。這兩種直覺的做法，正好就是今天要介紹的選擇排序和插入排序。再加上讓大的數字像泡泡一樣往後浮的氣泡排序，就是最基本的三種排序方法。

**排序（sorting）**是把一群資料依照某個欄位，由小到大（遞增）或由大到小（遞減）重新排列。資料排好之後，很多事情都會變簡單：查資料時可以用二分搜尋，每比一次就排除一半，只要 O(log n)；最大值、最小值就在頭尾；重複的資料也會排在一起，很容易找出來。

排序前先認識幾個名詞

• 鍵值（key）：排序時拿來比較的欄位。例如學生資料可以依學號排序，也可以依成績排序；同一批資料，鍵值不同，排出來的順序也不同。以下的例子都是整數，數字本身就是鍵值。
• 內部排序與外部排序：資料可以全部放進主記憶體排序的，稱為內部排序（internal sort）；資料太多，只能放在磁碟上分批讀進來處理的，稱為外部排序（external sort）。今天要介紹的都是屬於內部排序。
• 穩定性（stability）：鍵值相同的資料，排序後仍維持原本的先後順序，就稱為穩定排序。例如一份成績單先依姓名排好，再依分數排序；如果排序方法是穩定的，同分的學生仍會依姓名排列。
• 原地排序（in-place sort）：除了存放資料的陣列，只需要固定幾個暫存變數，額外空間是 O(1)。有些資料把只多用 O(log n) 空間的方法也算進來，這裡採用比較嚴格的 O(1) 說法。

要比較排序方法的快慢，通常看兩件事：比較次數（兩筆資料比大小幾次）和搬移次數（資料換位置幾次）。以下 n 代表資料筆數，範例都是把 8 筆整數由小到大排序：

26  59  1  61  5  15  11  37

選擇排序：每次挑出最小的

**選擇排序（selection sort）**的規則是：

1. 在還沒排好的資料中，找出最小值。
2. 把最小值和「還沒排好的部分」的第一筆交換。
3. 排好的部分多了一筆，對剩下的資料重複步驟 1、2，直到只剩一筆。

每一輪的結果如下，| 左邊是已經排好的部分：

只剩最後一筆時，它一定是最大的，所以 8 筆資料只要 7 輪。

比較次數是固定的。 第 1 輪要在 8 筆中找最小值，比較 7 次；第 2 輪比較 6 次……最後一輪比較 1 次，總共 7 + 6 + … + 1 = 28 次。一般來說是 (n − 1) + (n − 2) + … + 1 = n(n − 1) / 2 次。不管資料原本是亂的還是已經排好，每一輪都得把剩下的資料看完，才能確定誰最小，所以時間一律是 O(n²)。

但選擇排序的優點是交換次數少：每輪最多交換一次，總共不超過 n − 1 次。如果搬動一筆資料的代價很高，例如每筆資料很大，這個特性就有用。

選擇排序不穩定，因為交換可能改變相同數字的先後順序。例如「紅 5、黑 5、2」，把 2 和紅 5 交換後，變成「2、黑 5、紅 5」，兩張 5 的順序就反過來了。

插入排序：像整理手上的牌

**插入排序（insertion sort）**就像一張一張摸牌：左手的牌永遠是排好的，每摸到一張新牌，就把它插進正確的位置。

1. 第一筆資料單獨一筆，本身就算排好了。
2. 取出下一筆資料（稱為 key），由右往左和已排好的資料比較，比 key 大的都往右搬一格。
3. 遇到不比 key 大的資料，或已經到了最左邊，就停下來，把 key 放進空出來的位置。
4. 重複步驟 2、3，直到最後一筆。

以第 6 輪為例，前 6 筆已經排好，要插入的 key 是 11：

步驟 2 的「往右搬」，和在陣列中間插入資料時，把後面的資料往右移的做法相同：要從右往左搬，才不會蓋掉還沒搬的資料。完整的 7 輪如下：

要注意，插入排序 | 左邊的資料只是「彼此之間排好了」，位置還可能被後面插進來的資料擠動，例如 26 在第 2 輪後排在第 2 個，最後卻在第 5 個。這點和選擇排序不同，選擇排序每一輪排好的那一筆就是最終位置。

插入排序的時間取決於資料原本有多亂。

• 最好的情況：資料已經排好。每一輪 key 只和左邊一筆比較，發現不比它大就停，總共 n − 1 次比較，時間是 O(n)。
• 最壞的情況：資料完全相反。每個 key 都比左邊所有資料小，第 k 輪要比較 k 次、搬 k 次，總共 n(n − 1) / 2 次，時間是 O(n²)。

插入排序是穩定的。 往左比較時，遇到「不比 key 大」的資料就停下來，相等的資料不會被跨過去，原本在前面的仍然在前面。

氣泡排序：大的往後浮

**氣泡排序（bubble sort）**每一輪都從頭開始，兩兩比較相鄰的資料，如果前面比後面大就交換。這樣一路比到最後，最大的資料會被一路推到最後面，就像水中的氣泡往上浮。

第 1 輪結束，最大的 61 已經到了最後的位置，下一輪只要比到倒數第二筆就好。每一輪的結果如下，| 右邊是已經到達最終位置的資料：

第 5 輪從頭比到尾都沒有交換，代表每一對相鄰資料都已經是小的在前，整個陣列已經排好，可以提早結束，不必做滿 7 輪。總比較次數是 7 + 6 + 5 + 4 + 3 = 25 次。

• 最好的情況：資料已經排好，第 1 輪比較 n − 1 次、沒有交換，馬上結束，時間是 O(n)。這要靠「有沒有交換」的檢查；沒有這個檢查的版本，一定會做滿 n − 1 輪，最好的情況也是 O(n²)。
• 最壞的情況：資料完全相反，每一輪都有交換，總共比較 n(n − 1) / 2 次，時間是 O(n²)。

氣泡排序是穩定的。 只有前面「大於」後面才交換，相等的兩筆不會互換。

用程式比一比

下面的程式把三種排序寫成函式，每個函式都回傳比較了幾次，再分別對亂序、已排好、完全相反三組資料排序：

#include <stdbool.h>
#include <stdio.h>

#define SIZE 8

void printArray(const int data[], int length) {
    for (int i = 0; i < length; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
}

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

/* 選擇排序：每一輪從未排序區挑出最小值，換到未排序區的最前面 */
int selectionSort(int data[], int length) {
    int comparisons = 0;

    for (int i = 0; i < length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < length; j++) {
            comparisons++;
            if (data[j] < data[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            swap(&data[i], &data[minIndex]); /* 最小值已在原位時，不用交換 */
        }
    }
    return comparisons;
}

/* 插入排序：把下一筆資料插進前面已排好的部分，比它大的往右搬 */
int insertionSort(int data[], int length) {
    int comparisons = 0;

    for (int i = 1; i < length; i++) {
        int key = data[i];
        int j = i - 1;

        while (j >= 0) {
            comparisons++;
            if (data[j] <= key) {
                break;
            }
            data[j + 1] = data[j];
            j--;
        }
        data[j + 1] = key;
    }
    return comparisons;
}

/* 氣泡排序：相鄰兩筆比較，前面比較大就交換；一整輪沒有交換就提早結束 */
int bubbleSort(int data[], int length) {
    int comparisons = 0;

    for (int i = 0; i < length - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < length - 1 - i; j++) {
            comparisons++;
            if (data[j] > data[j + 1]) {
                swap(&data[j], &data[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
    return comparisons;
}

void copyArray(int target[], const int source[], int length) {
    for (int i = 0; i < length; i++) {
        target[i] = source[i];
    }
}

int main(void) {
    const int inputs[3][SIZE] = {
        {26, 59, 1, 61, 5, 15, 11, 37},
        {1, 5, 11, 15, 26, 37, 59, 61},
        {61, 59, 37, 26, 15, 11, 5, 1},
    };
    const char *names[3] = {"亂序", "已排好", "完全相反"};
    int data[SIZE];

    for (int k = 0; k < 3; k++) {
        printf("輸入（%s）：", names[k]);
        printArray(inputs[k], SIZE);

        copyArray(data, inputs[k], SIZE);
        int count = selectionSort(data, SIZE);
        printf("  選擇排序 比較 %2d 次：", count);
        printArray(data, SIZE);

        copyArray(data, inputs[k], SIZE);
        count = insertionSort(data, SIZE);
        printf("  插入排序 比較 %2d 次：", count);
        printArray(data, SIZE);

        copyArray(data, inputs[k], SIZE);
        count = bubbleSort(data, SIZE);
        printf("  氣泡排序 比較 %2d 次：", count);
        printArray(data, SIZE);
    }
    return 0;
}

執行結果：

輸入（亂序）：26 59 1 61 5 15 11 37
  選擇排序 比較 28 次：1 5 11 15 26 37 59 61
  插入排序 比較 20 次：1 5 11 15 26 37 59 61
  氣泡排序 比較 25 次：1 5 11 15 26 37 59 61
輸入（已排好）：1 5 11 15 26 37 59 61
  選擇排序 比較 28 次：1 5 11 15 26 37 59 61
  插入排序 比較  7 次：1 5 11 15 26 37 59 61
  氣泡排序 比較  7 次：1 5 11 15 26 37 59 61
輸入（完全相反）：61 59 37 26 15 11 5 1
  選擇排序 比較 28 次：1 5 11 15 26 37 59 61
  插入排序 比較 28 次：1 5 11 15 26 37 59 61
  氣泡排序 比較 28 次：1 5 11 15 26 37 59 61

幾個值得注意的地方：

• 選擇排序三組都是 28 次，也就是 8 × 7 / 2，和資料原本的順序無關。
• 資料已經排好時，插入排序和氣泡排序都只比較 7 次（n − 1），這就是 O(n) 的最好情況。
• 資料完全相反時，三種方法都比較 28 次，是最壞的情況。
• 程式裡交換兩筆資料要用一個 temp 暫存，三個函式除了陣列本身，都只用了幾個變數，額外空間是 O(1)。

三種方法的比較

表中氣泡排序的最好情況，指的是有「沒有交換就提早結束」檢查的版本。選擇排序的比較次數固定，插入、氣泡排序在最壞情況下也要比較 n(n − 1) / 2 次，大約是 n² / 2。以這些情況來看，1 萬筆資料大約要比較 5 千萬次；資料量變成 10 倍，比較次數大約變成 100 倍。但資料已經排好時，插入、氣泡排序都只需要 n − 1 次比較。

雖然三種方法的最壞情況都是 O(n²)，但各有適合的情況：

• 插入排序在資料「幾乎排好」時，通常只需要少量比較與搬移；如果總搬移次數和 n 成正比，時間就接近 O(n)。資料量小或幾乎排好時，它常常是最實用的選擇，很多更快的排序方法在處理小段資料時，也會改用插入排序收尾。
• 選擇排序比較次數固定，但每輪最多交換一次，交換次數少，適合搬動資料代價很高的情況。
• 氣泡排序最容易理解，但每次只能把資料往旁邊挪一格，資料很亂時會做很多次交換，實務上較少使用。

小結

排序是依鍵值重新排列資料。選擇排序每輪挑最小值，插入排序把下一筆放進已排好的部分，氣泡排序則讓最大值一路往後移。三種方法都只需要 O(1) 額外空間，最壞時間都是 O(n²)；選擇排序交換少，插入、氣泡排序則能利用資料已排好的特性，而且是穩定排序。

今日重點：

• 排序依鍵值重新排列資料；資料全部放在主記憶體的是內部排序，要分批從磁碟讀寫的是外部排序。
• 穩定排序：鍵值相同的資料，排序後仍維持原本的先後順序。
• 選擇排序：每輪找出最小值，和未排序部分的第一筆交換；一律比較 n(n − 1) / 2 次，不穩定。
• 插入排序：取出下一筆，比它大的往右搬，再放進空位；已排好時 O(n)，穩定。
• 氣泡排序：相鄰兩筆比較、前大後小就交換，每輪最大值浮到最後；一輪沒有交換就提早結束，穩定。
• 三種方法的最壞情況都是 O(n²)，額外空間都是 O(1)。

這三種方法都得一筆一筆慢慢比，資料一多就吃不消。下一篇的快速排序換個思路：先挑一個數字當基準，比它小的站左邊、比它大的站右邊，再讓兩邊各自照做。它的名字就叫「快速」，到底有多快？又為什麼遇到已經排好的資料，反而會慢下來？