C++插入排序

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

具體來說，我們?cè)谖磁判騾^(qū)間選擇一個(gè)基準(zhǔn)元素，將該元素與其左側(cè)已排序區(qū)間的元素逐一比較大小，并將該元素插入到正確的位置。

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

圖 11-6   單次插入操作

算法流程

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

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

圖 11-7   插入排序流程

insertion_sort.cpp

/* 插入排序 */
void insertionSort(vector<int> &nums) {
    // 外循環(huán)：已排序元素?cái)?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] 向右移動(dòng)一位
            j--;
        }
        nums[j + 1] = base; // 將 base 賦值到正確位置
    }
}

算法特性

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

插入排序優(yōu)勢(shì)

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

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

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

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

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