C語言鏈表排序算法實現：選擇排序與冒泡排序詳解

單鏈表排序：節點交換 vs 數據交換

數據結構

typedef struct Student {
    char id[20];
    char name[30];
    float score;
} Student;

typedef struct Node {
    Student data;
    struct Node *next;
} Node;

Node *head;  // 全局頭指針

核心抉擇：交換節點還是交換數據？

• 交換數據 (data)：代碼簡單，但若結構體大 (含大數組/字符串) 效率低；若節點被外部指針引用，交換數據不影響外部引用。
• 交換節點 (調整指針)：高效通用，但邏輯複雜，需處理頭節點、相鄰節點、前驅查找等邊界情況。
• 教學/中小數據量：推薦交換數據，邏輯清晰，易於理解排序本質。

選擇排序 (交換數據版)

void selection_sort_by_id() {
    for (Node *p = head; p; p = p->next) {
        Node *min = p;
        for (Node *q = p->next; q; q = q->next)
            if (strcmp(q->data.id, min->data.id) < 0)
                min = q;
        if (min != p) {
            Student tmp = p->data;
            p->data = min->data;
            min->data = tmp;
        }
    }
}

時間 O(n²)，空間 O(1)，不穩定排序。

冒泡排序 (交換數據版)

void bubble_sort_by_id() {
    int swapped;
    do {
        swapped = 0;
        for (Node *p = head; p && p->next; p = p->next) {
            if (strcmp(p->data.id, p->next->data.id) > 0) {
                Student tmp = p->data;
                p->data = p->next->data;
                p->next->data = tmp;
                swapped = 1;
            }
        }
    } while (swapped);
}

優化：每輪將最大元素「冒泡」到末尾，可記錄最後交換位置縮短下輪範圍。

進階：歸併排序 (O(n log n)，鏈表最適合)

// 分割：快慢指針找中點
Node *split(Node *head) {
    Node *slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    Node *mid = slow->next;
    slow->next = NULL;
    return mid;
}

// 合併兩個有序鏈表
Node *merge(Node *a, Node *b) {
    Node dummy, *tail = &dummy;
    while (a && b) {
        if (strcmp(a->data.id, b->data.id) <= 0) {
            tail->next = a; a = a->next;
        } else {
            tail->next = b; b = b->next;
        }
        tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

// 歸併排序入口
Node *merge_sort(Node *head) {
    if (!head || !head->next) return head;
    Node *mid = split(head);
    Node *left = merge_sort(head);
    Node *right = merge_sort(mid);
    return merge(left, right);
}

// 調用：head = merge_sort(head);

歸併排序是鏈表首選算法：穩定、O(n log n)、無需隨機訪問、遞歸棧深度 O(log n)。

總結建議

1. 作業/考試要求選擇/冒泡 → 實現數據交換版，代碼短、不易錯。
2. 實際項目/大數據量 → 直接用歸併排序 (或轉陣列 qsort 再重建)。
3. 若必須交換節點指針 → 畫圖理清 prev->next = curr->next; curr->next = next->next; ... 邏輯，分別處理頭節點、相鄰、非相鄰三種情況。