數據結構：C語言實現直接插入排序（Straight Insertion Sort）完整教學

直接插入排序核心思想

將數組分為有序區與無序區。初始有序區僅含第一個元素，每次從無序區取出首元素，在有序區中從後向前掃描，找到插入位置並移動元素騰出空位，完成插入。

• 時間複雜度：O(n²)
• 空間複雜度：O(1)
• 穩定排序：相等元素不交換順序
• 最好情況 O(n)：已有序數組只需比較無移動

標準實現代碼

#include <stdio.h>
#include <stdlib.h>

#define N 10

void insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; i++) {        // 從第 2 個元素開始
        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;                // 插入正確位置
    }
}

void print_array(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前: "); print_array(arr, n);
    insertion_sort(arr, n);
    printf("排序後: "); print_array(arr, n);
    return 0;
}

執行流程圖解（以 {9, 8, 7, 6, 5} 前 5 個為例）

步驟	有序區	待插入	比較/移動過程	結果
1	[9]	8	9>8 → 9 右移 → 插入 8	[8, 9]
2	[8, 9]	7	9>7→右移, 8>7→右移 → 插入 7	[7, 8, 9]
3	[7, 8, 9]	6	9,8,7 依次右移 → 插入 6	[6, 7, 8, 9]
4	[6, 7, 8, 9]	5	9,8,7,6 依次右移 → 插入 5	[5, 6, 7, 8, 9]

關鍵實現細節

1. 哨兵優化：可在 `arr[0]` 設置哨兵，省去 `j >= 0` 判斷（需額外空間）
2. 二分查找插入位置：將查找從 O(n) 降為 O(log n)，但移動仍為 O(n)，稱為二分插入排序
3. 原地移動：`arr[j+1] = arr[j]` 覆蓋式右移，無需額外交換變數

二分插入排序優化版

void binary_insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int low = 0, high = i - 1;
        // 二分查找插入位置
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] > key) high = mid - 1;
            else low = mid + 1;
        }
        // 統一右移 [low, i-1]
        for (int j = i - 1; j >= low; j--) arr[j + 1] = arr[j];
        arr[low] = key;
    }
}

三大基礎排序對比（補充插入排序視角）

| 維度 | 插入排序 | 選擇排序 | 冒泡排序 | |------|----------|----------|----------| | 核心操作 | **查找+移動** | 查找最小+交換 | 相鄰比較+交換 | | 近乎有序表現 | **極佳 O(n)** | 差 O(n²) | 優 O(n) | | 穩定性 | **穩定** | 不穩定 | 穩定 | | 寫入次數 | O(n²) | **最少 O(n)** | O(n²) | | 適用場景 | 小規模、近乎有序、線上排序 | 寫入昂貴存儲 | 教學、極小數據 |

實戰應用場景

• 線上排序：數據流式到達，隨到隨插（如維護有序容器）
• 混合排序閾值：快速排序/歸併排序處理小區間（通常 n < 32）時切換到插入排序
• 殼排序基礎：希爾排序本質是分組插入排序

總結

直接插入排序以穩定、適應性強（有序度高時極快）、實現簡潔著稱，是工程中小規模排序、混合排序基例的首選算法。