「插入排序 insertion sort」是一種簡單的排序算法，它的工作原理與手動整理一副牌的過程非常相似。

具體來說，我們在未排序區(qū)間選擇一個基準元素，將該元素與其左側(cè)已排序區(qū)間的元素逐一比較大小，并將該元素插入到正確的位置。

圖 11-6 展示了數(shù)組插入元素的操作流程。設基準元素為 base ，我們需要將從目標索引到 base 之間的所有元素向右移動一位，然后再將 base 賦值給目標索引。

圖 11-6   單次插入操作

算法流程

插入排序的整體流程如圖 11-7 所示。

1. 初始狀態(tài)下，數(shù)組的第 1 個元素已完成排序。
2. 選取數(shù)組的第 2 個元素作為 base ，將其插入到正確位置后，數(shù)組的前 2 個元素已排序。
3. 選取第 3 個元素作為 base ，將其插入到正確位置后，數(shù)組的前 3 個元素已排序。
4. 以此類推，在最后一輪中，選取最后一個元素作為 base ，將其插入到正確位置后，所有元素均已排序。

圖 11-7   插入排序流程

insertion_sort.cpp

/* 插入排序 */
void insertionSort(vector<int> &nums) {
    // 外循環(huán)：已排序元素數(shù)量為 1, 2, ..., n
    for (int i = 1; i < nums.size(); i++) {
        int base = nums[i], j = i - 1;
        // 內(nèi)循環(huán)：將 base 插入到已排序部分的正確位置
        while (j >= 0 && nums[j] > base) {
            nums[j + 1] = nums[j]; // 將 nums[j] 向右移動一位
            j--;
        }
        nums[j + 1] = base; // 將 base 賦值到正確位置
    }
}

算法特性

• 時間復雜度 $O(n^2)$、自適應排序：最差情況下，每次插入操作分別需要循環(huán) $n?1$ 、$n?2$、 $\dots$ 、$2$、 $1$ 次，求和得到 $(n?1)n/2$ ，因此時間復雜度為 $O(n^2)$ 。在遇到有序數(shù)據(jù)時，插入操作會提前終止。當輸入數(shù)組完全有序時，插入排序達到最佳時間復雜度 $O(n)$ 。
• 空間復雜度 $O(1)$、原地排序：指針 $i$ 和 $j$ 使用常數(shù)大小的額外空間。
• 穩(wěn)定排序：在插入操作過程中，我們會將元素插入到相等元素的右側(cè)，不會改變它們的順序。

插入排序優(yōu)勢

插入排序的時間復雜度為 $O(n^2)$ ，而我們即將學習的快速排序的時間復雜度為 $O(n\log ?n)$ 。盡管插入排序的時間復雜度相比快速排序更高，但在數(shù)據(jù)量較小的情況下，插入排序通常更快。

這個結(jié)論與線性查找和二分查找的適用情況的結(jié)論類似。快速排序這類 $O(n\log ?n)$ 的算法屬于基于分治的排序算法，往往包含更多單元計算操作。而在數(shù)據(jù)量較小時，$n^2$ 和 $n\log ?n$ 的數(shù)值比較接近，復雜度不占主導作用；每輪中的單元操作數(shù)量起到?jīng)Q定性因素。

實際上，許多編程語言（例如 Java）的內(nèi)置排序函數(shù)都采用了插入排序，大致思路為：對于長數(shù)組，采用基于分治的排序算法，例如快速排序；對于短數(shù)組，直接使用插入排序。

雖然冒泡排序、選擇排序和插入排序的時間復雜度都為 O(n2) ，但在實際情況中，插入排序的使用頻率顯著高于冒泡排序和選擇排序，主要有以下原因。

• 冒泡排序基于元素交換實現(xiàn)，需要借助一個臨時變量，共涉及 3 個單元操作；插入排序基于元素賦值實現(xiàn)，僅需 1 個單元操作。因此，冒泡排序的計算開銷通常比插入排序更高。
• 選擇排序在任何情況下的時間復雜度都為 O(n2) 。如果給定一組部分有序的數(shù)據(jù)，插入排序通常比選擇排序效率更高。
• 選擇排序不穩(wěn)定，無法應用于多級排序。