I. 插入排序與選擇排序

考卷很愛給你一段排序程式碼，再問「跑完第幾輪的時候，陣列長什麼樣子」。11.10 的泡沫排序是其中一種，另外兩位常客是插入排序與選擇排序。三種的規則都只有一句話，抓住那句話就追得動整張表。

下面兩支程式都拿同一組資料 $5, 2, 4, 1, 3$ 開場，每跑完一輪就把整個陣列印出來，方便左右對照。

¶插入排序：把手上這張牌往前插

規則：從左邊第二個數開始，每個數往前找到自己該待的位置插進去。就像打撲克牌整理手牌——新抽到的牌往左邊一張一張比，比它大的通通往右讓一格，讓出來的縫隙就是它的位置。左邊那一段永遠是排好的。

#include <iostream>
using namespace std;

int main() {
    int a[5] = {5, 2, 4, 1, 3};
    int n = 5;

    for (int i = 1; i < n; i++) {
        int key = a[i];                     // 手上這張牌
        int j = i - 1;
        while (j >= 0 && a[j] > key) {      // 比 key 大的，通通往右挪一格
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;                     // 空出來的位置就是 key 的家

        for (int k = 0; k < n; k++) {       // 印出這一輪結束後的樣子
            if (k > 0) cout << ' ';
            cout << a[k];
        }
        cout << '\n';
    }
    return 0;
}

執行結果：

輪次	手上這張牌	這一輪結束後
第 $1$ 輪	$2$	$2, 5, 4, 1, 3$
第 $2$ 輪	$4$	$2, 4, 5, 1, 3$
第 $3$ 輪	$1$	$1, 2, 4, 5, 3$
第 $4$ 輪	$3$	$1, 2, 3, 4, 5$

第 $3$ 輪的 $1$ 比左邊那段都小，於是 $2, 4, 5$ 整段往右挪一格， $1$ 插到最前面。

¶選擇排序：每輪挑最小的換到前面

規則：每一輪從還沒排好的那一段裡找出最小的，跟這一段的第一格交換。左邊每輪確定一格，而且整輪只交換一次。

#include <iostream>
using namespace std;

int main() {
    int a[5] = {5, 2, 4, 1, 3};
    int n = 5;

    for (int i = 0; i < n - 1; i++) {
        int minPos = i;                     // 先假設第 i 格最小
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minPos]) {
                minPos = j;                 // 找到更小的，記住它在哪
            }
        }
        int t = a[i];                       // 把最小的換到第 i 格
        a[i] = a[minPos];
        a[minPos] = t;

        for (int k = 0; k < n; k++) {       // 印出這一輪結束後的樣子
            if (k > 0) cout << ' ';
            cout << a[k];
        }
        cout << '\n';
    }
    return 0;
}

執行結果：

輪次	找到的最小值	這一輪結束後
第 $1$ 輪	$1$	$1, 2, 4, 5, 3$
第 $2$ 輪	$2$	$1, 2, 4, 5, 3$
第 $3$ 輪	$3$	$1, 2, 3, 5, 4$
第 $4$ 輪	$4$	$1, 2, 3, 4, 5$

第 $2$ 輪印出來的跟第 $1$ 輪一模一樣——這一輪找到的最小值 $2$ 本來就待在該待的位置，於是跟自己交換。追蹤題很喜歡拿這種「看起來沒動」的一輪當陷阱。

外層只跑 $n - 1$ 輪：最後一格不必再挑，剩下的那個自動是最大的。中間那三行 int t = a[i]; 是 C 的交換寫法（A 節對照表的最後一列，也就是上冊 3.9 用過的那招）。

¶三種排序一次看完

演算法	每一輪在做什麼	這一輪結束後定案的部分
泡沫排序	相鄰兩個兩個比，把最大的一路換到最右邊	右邊多一格（最大的），不會再變
插入排序	把一個新數插進左邊已經排好的那一段	左邊那段是排好的，但還會被後面的數擠開
選擇排序	從還沒排好的數裡挑最小的，換到最前面	左邊多一格（最小的），不會再變

三種都是兩層迴圈，最壞情況都要 $n^2$ 量級的次數（ $O(n^2)$ ，記號見 10.1）。考卷考的是你追不追得動這張表，不是誰比較快——真的要排序，用 11.4 的 sort 就好。

← H. char * 當字串 — 已是最後一節 —