排序與搜尋
插入排序
插入排序正是大多數人整理手中撲克牌的方式：在左側留一段整齊的已排序牌，然後拿起下一張，把它往左滑過所有比它大的牌，落到它該在的位置。重複，直到未排序的那堆牌沒了。任何時刻，左半部分都是完全有序的；你只是一張一張地把它擴大。
從機制上看，你從左到右掃過陣列。對每個新元素，把它和身後那些已排序的元素比較，把太大的那些各往右挪一格，騰出一個空位讓新元素落進去。真正幹活的就是這個挪動，而挪動的多少完全取決於資料本來有多亂。
在近乎有序的資料上，它表現極好：每個元素幾乎不用動，代價趨近 O(n)——最好情況（已經有序）正好是 O(n)。但平均情況、以及最壞情況（完全逆序）下，元素要走很遠，代價是 O(n^2)。它原地排序，額外空間 O(1)，而且穩定（相等的鍵保持原來的先後順序）。對小規模或幾乎有序的輸入，它很難被超越，所以現實中的排序庫會在子陣列很小時退回用它。
void insertionSort(std::vector<int>& a) {
for (int i = 1; i < (int)a.size(); ++i) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) { // shift bigger ones right
a[j + 1] = a[j];
--j;
}
a[j + 1] = key; // drop key into the gap
}
}把 key 暫存一旁，較大的元素右移，給它騰出位置。
穩定 + 原地 + 自適應（對近乎有序的資料很快），這三點兼得很少見。這正是 Timsort 和許多 std::sort 實作在子陣列縮小到某個小閾值之下時改用插入排序的原因。
又稱
另見