鏈結串列排序演算法解析：適用性比較與插入排序實作範例

鏈結串列排序的特殊挑戰

陣列排序仰賴隨機存取（O(1) 索引），而鏈結串列僅能循序存取。這導致：

• 無法高效實現「雙向掃描」（快速排序 Partition、希爾排序間隔）。
• 無法 O(1) 存取中間元素（歸併排序找中點、堆排序建堆）。
• 指標操作錯誤極易導致記憶體錯誤（Segmentation Fault）。

八大排序演算法在鏈結串列上的適用性評估

結論：插入排序是單向鏈結串列的首選（穩定、適合近乎有序資料、指標操作直觀）。若追求 O(N log N)，歸併排序（自底向上迭代版）是鏈表的最佳選擇。

插入排序完整實作（節點重鏈接法）

核心思想：將原串列拆分為已排序部分（`sorted`）與待排序部分（`curr`），逐一取出 `curr` 節點插入 `sorted` 正確位置。

節點結構

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

主排序函式

void sort_for_link_node(NODE** ppHead) {
    if (NULL == ppHead || NULL == *ppHead) return;

    NODE* sorted = *ppHead;       // 已排序部分初始只有頭節點
    NODE* curr = sorted->next;    // 待排序部分從第二個開始
    sorted->next = NULL;          // 切斷連結，sorted 成為獨立有序串列

    while (curr) {
        NODE* next = curr->next;  // 保存下一個待處理節點
        insert_for_sort_operation(&sorted, curr); // 插入有序串列
        curr = next;
    }

    *ppHead = sorted; // 更新頭指標
}

有序插入核心邏輯

void insert_for_sort_operation(NODE** ppSortedHead, NODE* pNode) {
    pNode->next = NULL; // 斷開節點原連結

    // 情況 1：插入新頭節點（值小於當前頭）
    if (pNode->data < (*ppSortedHead)->data) {
        pNode->next = *ppSortedHead;
        *ppSortedHead = pNode;
        return;
    }

    // 情況 2：在中間或尾部尋找插入點
    NODE* prev = *ppSortedHead;
    NODE* cur = prev->next;

    while (cur && pNode->data >= cur->data) {
        prev = cur;
        cur = cur->next;
    }

    // 插入：prev -> pNode -> cur
    prev->next = pNode;
    pNode->next = cur;
}

關鍵指標操作圖解

插入前:  sorted: 3 -> 5 -> 8 -> NULL
         pNode: 6

尋找過程: prev=5, cur=8 (6 < 8 停止)

插入後:  prev->next = pNode (5->6)
         pNode->next = cur   (6->8)
         結果: 3 -> 5 -> 6 -> 8 -> NULL

複雜度與特性

• 時間：O(N²) 最壞/平均；O(N) 最佳（已有序）。
• 空間：O(1) 原地排序。
• 穩定性：穩定（相等元素不交換順序）。
• 適用場景：小規模資料、近乎有序資料、線上排序（串流輸入）。

總結

鏈結串列排序的本質是指標重組而非資料搬移。插入排序以其單向掃描、局部指標調整的特性，完美契合單向鏈表的存取模式。實作時務必注意：保存 `next` 指標再斷開、處理頭節點插入特例、正確重鏈 `prev->next` 與 `pNode->next`，這三步驟缺一不可。