插入排序變體：靜態鏈表實現的表插入排序

算法思想

表插入排序利用靜態鏈表結構，分兩階段完成：

1. 邏輯排序：構建有序循環鏈表，僅修改指針，不移動數據
2. 物理重排：按鏈表順序將數據回寫數組，實現物理有序

數據結構設計

const int MAX = 1000; // 需大於等於最大可能值

typedef struct {
    int data;  // 數據域
    int next;  // 指針域（下標索引）
} Rec;

核心實現

void InsertSort(int a[], int n) {
    Rec* rec = new Rec[n + 1];

    // 初始化數據
    for (int i = 0; i < n; ++i) {
        rec[i + 1].data = a[i];
        rec[i + 1].next = 0;
    }

    // 頭節點：值設為 MAX，next 指向第一個元素
    rec[0].data = MAX;
    rec[0].next = 1; // 首元素與頭節點構成初始循環鏈表

    // 逐個插入構建有序鏈表
    for (int i = 2; i <= n; ++i) {
        int q = 0;
        int p = rec[q].next;

        // 尋找插入位置（>= 保證穩定性）
        while (rec[i].data >= rec[p].data) {
            q = p;
            p = rec[q].next;
        }

        // 插入節點 i
        rec[i].next = p;
        rec[q].next = i;
    }

    // 按鏈表順序回寫數組
    int p = rec[0].next;
    int idx = 0;
    while (p != 0) {
        a[idx++] = rec[p].data;
        p = rec[p].next;
    }

    delete[] rec;
}

關鍵點解析

1. 頭節點設計：值為 MAX 確保所有數據都小於它，next=1 構建初始單元素循環
2. 插入邏輯：從頭遍歷，找到首個大於待插值的節點，插在其前驅後
3. 穩定性保證：使用 >= 比較，相等元素插在現有元素後
4. 空間換時間：O(n) 輔助空間，避免了數據移動開銷

複雜度分析

• 時間：O(n²)（查找插入位置）
• 空間：O(n)
• 數據移動：0（邏輯階段），n 次（物理重排階段）

適用場景

記錄較大、關鍵字較小的數據集；作為教學示例展示指針操作與排序思想結合。

擴展思考

物理重排階段可優化為原地重排，進一步減少空間開銷。讀者可嘗試實現：沿鏈表遍歷，將節點交換到正確物理位置並同步更新指針。