C語言鏈表選擇排序實現：結構體數組字段比較、升序降序完整代碼

編輯：關於C語言

場景描述

單向鏈表節點包含結構體數組字段（如 `char id[12]`、`char name[20]`），需按指定字段（如 `id`）進行選擇排序，支持升序/降序。

節點結構

typedef struct Student {
    char id[12];
    char name[20];
    struct Student *next;
} Student;

核心比較與交換工具

字符串比較：`strcmp(a, b)` 返回 `<0`/`=0`/`>0`
字符串複製：`strcpy(dest, src)` 逐字符複製（不可直接賦值數組）
交換策略：交換節點數據域而非指針，避免複雜指針重連

升序選擇排序實現

Student *list_sort_asc(Student *head) {
    Student *tail = head->next;          // 當前有序區尾部
    Student *curr;
    Student tmp;                         // 臨時結構體用於交換

    while (tail) {
        curr = tail->next;               // 掃描無序區
        while (curr) {
            // tail->id > curr->id 返回 >0，說明 curr 更小，需交換
            if (strcmp(tail->id, curr->id) > 0) {
                // 交換兩節點的所有數據字段
                strcpy(tmp.id, tail->id);
                strcpy(tmp.name, tail->name);

                strcpy(tail->id, curr->id);
                strcpy(tail->name, curr->name);

                strcpy(curr->id, tmp.id);
                strcpy(curr->name, tmp.name);
            }
            curr = curr->next;
        }
        tail = tail->next;  // 有序區擴展
    }
    return head;
}

降序選擇排序實現

Student *list_sort_desc(Student *head) {
    Student *tail = head->next;
    Student *curr;
    Student tmp;

    while (tail) {
        curr = tail->next;
        while (curr) {
            // tail->id < curr->id 返回 <0，說明 curr 更大，需交換
            if (strcmp(tail->id, curr->id) < 0) {
                strcpy(tmp.id, tail->id);
                strcpy(tmp.name, tail->name);

                strcpy(tail->id, curr->id);
                strcpy(tail->name, curr->name);

                strcpy(curr->id, tmp.id);
                strcpy(curr->name, tmp.name);
            }
            curr = curr->next;
        }
        tail = tail->next;
    }
    return head;
}

算法邏輯圖解（選擇排序於鏈表）

初始:  head → [1003] → [1001] → [1002] → NULL
             ↑tail
第1輪掃描無序區 [1001] [1002]：
  發現 1001 < 1003 → 交換 tail(1003) 與 1001
  發現 1002 < 1001 → 交換 tail(1001) 與 1002
結果:  head → [1002] → [1003] → [1001] → NULL
             ↑tail
第2輪尾部後移，掃描 [1003] [1001]...
最終:  head → [1001] → [1002] → [1003] → NULL  (升序)

打印鏈表驗證

void print_list(Student *head) {
    for (Student *p = head->next; p; p = p->next)
        printf("[%s] %s\n", p->id, p->name);
}

關鍵點總結

| 要點 | 說明 | |------|------| | **數據域交換** | 鏈表選擇排序最簡單方式是交換 `id`、`name` 等數據域，而非調整 `next` 指針 | | **strcmp 返回值** | `<0`：左小；`=0`：相等；`>0`：左大。升序用 `>0` 觸發交換，降序用 `<0` | | **臨時結構體** | `Student tmp` 用於三步交換，避免數據覆蓋 | | **時間複雜度** | O(n²) 比較 + O(n²) 字符串複製。小規模鏈表可接受 | | **穩定性** | 選擇排序**不穩定**，相同 `id` 的節點相對順序可能改變 |

優化方向

指針重連排序：交換節點指針而非數據，避免 `strcpy` 開銷（適合大數據域）

歸併排序

索引輔助

歸併排序鏈表框架（高效替代）

// 分割鏈表為兩半（快慢指針）
Student *split(Student *head) {
    Student *slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    Student *mid = slow->next;
    slow->next = NULL;
    return mid;
}

// 合併兩有序鏈表
Student *merge(Student *a, Student *b) {
    Student dummy, *tail = &dummy;
    while (a && b) {
        if (strcmp(a->id, b->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;
}

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