鏈表排序演算法選型與插入排序 C 實現詳解

鏈表因非連續記憶體、無隨機訪問特性，排序演算法選型與陣列大異。本文分析八大經典排序在鏈表上的適用性，並給出插入排序完整實現。

鏈表排序適用性速查表

核心原則：僅涉及數據交換的排序適合鏈表；需中間值、隨機訪問、下標運算的不適合。

插入排序鏈表版完整實現

typedef struct Node {
    int data;
    struct Node* next;
} NODE;

// 將 pNode 插入以 ppHead 為頭的有序鏈表中
void insertSorted(NODE** ppHead, NODE* pNode) {
    pNode->next = NULL;  // 斷開原鏈接
    
    // 插入頭部
    if (!*ppHead || pNode->data < (*ppHead)->data) {
        pNode->next = *ppHead;
        *ppHead = pNode;
        return;
    }
    
    // 尋找插入位置
    NODE* cur = *ppHead;
    while (cur->next && pNode->data >= cur->next->data)
        cur = cur->next;
    
    pNode->next = cur->next;
    cur->next = pNode;
}

// 主排序函數：原地插入排序
void sortList(NODE** ppHead) {
    if (!ppHead || !*ppHead) return;
    
    NODE* sorted = *ppHead;   // 已排序部分頭
    NODE* curr = sorted->next; // 待排序部分頭
    sorted->next = NULL;       // 斷開
    
    while (curr) {
        NODE* next = curr->next;  // 保存下一個
        insertSorted(&sorted, curr);
        curr = next;
    }
    *ppHead = sorted;
}

關鍵細節解析

1. 斷開重連：將原鏈表拆為「已排序」與「待排序」兩部分鏈表，避免遍歷時陷入循環。
2. 指針傳址：NODE** 允許修改頭指針（插入新最小值時）。
3. 保存 next：在調用 insertSorted 前保存 curr->next，因插入過程會修改 curr->next。
4. 穩定性：使用 >= 判斷插入位置，保證相等元素相對順序不變（穩定排序）。

複雜度

• 時間：O(n²) 最壞/平均，O(n) 最佳（已有序）。
• 空間：O(1) 原地排序。

工程建議

若鏈表長度 > 1000，建議先轉陣列（或 vector）用 O(n log n) 排序，再重建鏈表；或實現鏈表版歸併排序（遞歸分割 + 合併），雖代碼較長但穩定 O(n log n)。