排序（一）：簡單排序

插入排序：你理撲克牌的方式

插入排序正是大多數人理一手牌的方式。讓陣列的左半部分保持有序；取下一個元素，把它向左滑過所有比它大的，直到落入正確位置。每走一步，有序區就增長一個。

Sorting [ 5  2  4  1 ] by insertion (| marks end of sorted region):

  [ 5 | 2  4  1 ]   take 2, slide past 5     -> [ 2  5 | 4  1 ]
  [ 2  5 | 4  1 ]   take 4, slide past 5     -> [ 2  4  5 | 1 ]
  [ 2  4  5 | 1 ]   take 1, slide to front   -> [ 1  2  4  5 | ]
  done.

每一趟把一個元素插入到已經有序的左側區域。

void insertionSort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) { // slide larger ones right
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;               // drop key into the gap
    }
}

在近乎有序的輸入上，內層迴圈幾乎不動——接近 O(n)。

選擇與氣泡，略說

選擇排序反覆掃描未排序部分，找出最小元素並把它交換到前面。氣泡排序反覆走過陣列，交換相鄰的逆序對，於是大的值"冒"到末尾。三者都是簡單的嵌套迴圈。

void selectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int m = i;                       // index of smallest in a[i..]
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[m]) m = j;
        std::swap(a[i], a[m]);           // put it at position i
    }
}

選擇排序：找最小，換到前面，重複。

選擇排序有一點做得好：它總共最多做 n−1 次交換——比其他兩種都少。如果交換遠比比較昂貴（大型記錄），這一點其實有用。氣泡排序在實踐中是三者裡最慢的，多半只作為教學例子保留，並不用於真實場景。

為何三者都是 O(n^2)

每一種在最壞情況下大約做 n 趟，每趟觸碰至多 n 個元素——嵌套迴圈，所以是 O(n^2) 次比較。輸入翻倍，工作量大約翻四倍。這對幾十的 n 沒問題，對百萬的 n 就很痛苦。

插入排序有個可愛的最好情況：在已經有序（或近乎有序）的資料上，內層 `while` 從不挪動任何東西，於是它以 O(n) 執行。選擇排序則不論輸入如何，總是做同樣的 n^2/2 次比較。

那為何還要教它們？

它們容易寫對——比快速排序更少藏 bug 的地方。
插入排序對小陣列和近乎有序的資料是真正的最佳選擇——真實的函式庫會在子陣列很小時切換到它。
它們的迴圈不變式和逐趟行為，培養出合併排序與快速排序將要倚靠的直覺。

下一篇我們用合併排序和快速排序突破 O(n^2) 的天花板——兩者都直接建立在上一篇的分治思想之上。