C 語言排序系列：插入排序原理與實現

插入排序是最直觀的排序算法之一，其核心思想是：將數組分為「已排序」與「未排序」兩部分，每次從未排序區取出一個元素，插入到已排序區的適當位置。

算法原理

• 時間複雜度：O(n²) —— 適合小規模或近乎有序的數據
• 空間複雜度：O(1) —— 原地排序
• 穩定性：穩定排序（相等元素相對順序不變）
• 適用場景：小數組、近乎有序數組、在線排序

核心邏輯

void InsertSort(int data[], int length) {
    for (int i = 1; i < length; ++i) {        // 從第 2 個元素開始
        for (int j = i; j > 0; --j) {         // 向前掃描已排序區
            if (data[j] < data[j - 1]) {      // 找到插入位置
                Swap(&data[j], &data[j - 1]); // 交換
            } else {
                break;                        // 已到達正確位置，提前退出
            }
        }
    }
}

完整可運行代碼

#include <stdio.h>

void Swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void InsertSort(int data[], int length) {
    for (int i = 1; i < length; ++i) {
        for (int j = i; j > 0; --j) {
            if (data[j] < data[j - 1]) {
                Swap(&data[j], &data[j - 1]);
            } else {
                break;
            }
        }
    }
}

int main() {
    int data[8] = {4, 7, 2, 6, 5, 9, 3, 8};
    InsertSort(data, 8);
    for (int i = 0; i < 8; ++i) {
        printf("%d ", data[i]);
    }
    printf("\n");
    return 0;
}

執行過程演示

初始：[4, 7, 2, 6, 5, 9, 3, 8]

• i=1：7 已在正確位置 → [4, 7, 2, 6, 5, 9, 3, 8]
• i=2：2 插入到開頭 → [2, 4, 7, 6, 5, 9, 3, 8]
• i=3：6 插入 4 和 7 之間 → [2, 4, 6, 7, 5, 9, 3, 8]
• ... 以此類推

最終：[2, 3, 4, 5, 6, 7, 8, 9]

優化方向

1. 二分查找插入位置：將內層線性查找優化為 O(log n)，但移動元素仍需 O(n)
2. 哨兵優化：減少邊界判斷
3. 希爾排序：插入排序的改進版，通過分組預排序大幅提升效率

總結

插入排序雖然不是大數據量的最優選，但代碼簡潔、穩定、適應性強，是每個程序員必須掌握的基礎算法。理解其「在線處理」特性，有助於靈活應對流式數據排序場景。