直接插入排序演算法：C++ 實作與效能分析

編輯：關於C語言

前言：簡單但實用的排序演算法

直接插入排序是原地、穩定、線性空間的排序演算法。雖然平均時間複雜度為 O(n²)，但對小規模資料、近乎有序、或線上排序 (資料逐筆到達) 場景極具優勢。本文提供標準 C++ 實作、效能特性分析與優化變體。

核心演算法邏輯

將陣列分為「已排序區間」與「未排序區間」
初始：已排序區間僅含第一個元素
每輪從未排序區間取第一個元素，插入已排序區間的適當位置
重複直到未排序區間為空

標準 C++ 實作

#include <iostream>
#include <vector>

void insertion_sort(std::vector<int>& arr) {
    const int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int key = arr[i];           // 待插入元素
        int j = i - 1;
        
        // 從右向左掃描已排序區間，將大於 key 的元素右移
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;           // 插入正確位置
    }
}

// 通用版本：支援任意型別與自訂比較
template <typename RandomIt, typename Compare = std::less<>>
void insertion_sort(RandomIt first, RandomIt last, Compare comp = {}) {
    for (auto it = first + 1; it != last; ++it) {
        auto key = *it;
        auto j = it;
        while (j != first && comp(key, *(j - 1))) {
            *j = *(j - 1);
            --j;
        }
        *j = key;
    }
}

完整可執行範例

#include <iostream>
#include <vector>

void print_array(const std::vector<int>& arr) {
    for (int v : arr) std::cout << v << ' ';
    std::cout << '\n';
}

int main() {
    std::vector<int> arr = {7, 3, 5, 8, 9, 1, 2, 4, 6};
    std::cout << "Before: "; print_array(arr);
    
    insertion_sort(arr);
    
    std::cout << "After:  "; print_array(arr);
    return 0;
}

/* 輸出：
Before: 7 3 5 8 9 1 2 4 6
After:  1 2 3 4 5 6 7 8 9
*/

效能特性分析

指標	數值	說明
最佳時間複雜度	O(n)	輸入已排序，內層迴圈零執行
平均時間複雜度	O(n²)	隨機輸入
最差時間複雜度	O(n²)	輸入逆序，每輪需掃描整個已排序區間
空間複雜度	O(1)	原地排序，僅需常數額外空間
穩定性	穩定	相等元素相對順序不變
適應性	高	近乎有序時極快

優化變體

1. 二分搜尋插入點 (Binary Insertion Sort)

將線性掃描改為二分搜尋，比較次數從 O(n) 降為 O(log n)，但移動次數仍為 O(n²)，總體複雜度不變，適合「比較昂貴、移動廉價」的型別。

template <typename RandomIt, typename Compare = std::less<>>
void binary_insertion_sort(RandomIt first, RandomIt last, Compare comp = {}) {
    for (auto it = first + 1; it != last; ++it) {
        auto key = *it;
        // 在 [first, it) 範圍二分搜尋插入點
        auto pos = std::lower_bound(first, it, key, comp);
        // 將 [pos, it) 右移一位
        std::move_backward(pos, it, it + 1);
        *pos = key;
    }
}

2. 哨兵優化 (減少邊界檢查)


void insertion_sort_sentinel(int* arr, int n) {
    for (int i = 1; i < n; ++i) {
        if (arr[i] < arr[i-1]) {
            int key = arr[i];
            int j = i - 1;
            arr[0] = key;  // 哨兵位置
            while (key < arr[j]) {
                arr[j+1] = arr[j];
                --j;
            }
            arr[j+1] = key;
        }
    }
}