無表頭單向鏈表的直接插入排序實現詳解

演算法核心思想

直接插入排序的基本邏輯：假設鏈表前 n-1 個節點已按關鍵字（本例以學號 num 為鍵值）由小到大排好序，對第 n 個節點在有序序列中尋找插入位置，使插入後序列仍有序。依此思想，從頭遍歷至尾，即可將無序鏈表轉為有序。

單向鏈表插入排序圖示邏輯

雖然圖示畫出兩條鏈表，實際操作只有一條鏈表。排序過程中，僅新增一個指標 first 指向待排序部分的頭節點：

1. 以原鏈表第一個節點為初始有序鏈表（head->next = NULL）。
2. first 指向原鏈表第二個節點（剩餘待排序部分）。
3. 從 first 取出節點，在有序鏈表中定位插入位置，完成插入。
4. first 後移，重複步驟 3，直到 first == NULL。

完整 C 語言實現

struct student *InsertSort(struct student *head) {
    struct student *first;  // 待排序部分的頭指標
    struct student *t;      // 待插入節點
    struct student *p;      // 插入位置的前驅節點
    struct student *q;      // 插入位置的當前節點

    first = head->next;     // 圖 12：剩餘待排序節點
    head->next = NULL;      // 圖 11：只含一個節點的有序鏈表

    while (first != NULL) {
        // 在有序鏈表中尋找插入位置：q 指向第一個鍵值 >= t 的節點
        for (t = first, q = head; (q != NULL) && (q->num < t->num); p = q, q = q->next);

        first = first->next;  // 關鍵：先將 t 從待排序鏈表摘除

        if (q == head) {      // 插在第一個節點之前（新頭節點）
            head = t;
        } else {              // 插在 p 與 q 之間
            p->next = t;
        }
        t->next = q;          // 完成插入
    }
    return head;
}

關鍵細節解析

1. first = first->next 的位置極其關鍵

註解中提到：「按道理這句話放在下面註釋位置也應該對，但是就是不能」。原因在於 t 就是 first 指向的節點，若先插入再更新 first，t->next 已被修改為 q，導致 first->next 取值錯誤。**必須在修改 t->next 之前保存下一個待處理節點。**

2. 為何不需要額外記憶體？

整個排序過程只是調整指標指向，並未配置新節點，空間複雜度 O(1)，是原地排序演算法。

3. 時間複雜度

• 最佳情況（已有序）：O(n)，每次插入位置在表尾，內層迴圈不執行。
• 最差情況（逆序）：O(n²)，每次插入位置在表頭，內層迴圈遍歷整個有序部分。
• 平均情況：O(n²)。

總結

無表頭單向鏈表的直接插入排序，核心在於「一條鏈表、兩個區域（有序/無序）、一個遊走指標」。理解 first 更新時機與插入邊界條件（插入表頭 vs 表中）是正確實現的關鍵。此演算法適合資料量較小或近乎有序的鏈表排序場景。