C++中如何實現鏈表的排序算法

# C++中如何實現鏈表的排序算法

## 目錄
1. [引言](#引言)
2. [鏈表基礎回顧](#鏈表基礎回顧)
3. [排序算法概述](#排序算法概述)
4. [鏈表排序的特殊性](#鏈表排序的特殊性)
5. [冒泡排序在鏈表中的實現](#冒泡排序在鏈表中的實現)
6. [選擇排序在鏈表中的實現](#選擇排序在鏈表中的實現)
7. [插入排序在鏈表中的實現](#插入排序在鏈表中的實現)
8. [歸并排序在鏈表中的實現](#歸并排序在鏈表中的實現)
9. [快速排序在鏈表中的實現](#快速排序在鏈表中的實現)
10. [性能比較與算法選擇](#性能比較與算法選擇)
11. [實際應用案例](#實際應用案例)
12. [總結](#總結)
13. [參考文獻](#參考文獻)

## 引言

鏈表作為基礎數據結構之一，在C++中有著廣泛的應用場景。與數組不同，鏈表通過指針連接各個節點，這種非連續存儲特性使得鏈表的排序算法實現與數組有顯著差異。本文將系統性地探討在C++中實現鏈表排序的各種方法，分析其時間復雜度、空間復雜度以及適用場景。

## 鏈表基礎回顧

### 鏈表結構定義
```cpp
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

鏈表特性

• 動態內存分配：節點在堆上動態創建
• 非連續存儲：物理地址不連續，僅通過指針邏輯連接
• 操作復雜度：
  • 插入/刪除：O(1)（已知位置時）
  • 隨機訪問：O(n)

排序算法概述

常見排序算法分類

鏈表排序的特殊性

與數組排序的主要差異

1. 隨機訪問限制：無法直接通過索引訪問元素
2. 指針操作：需要維護節點間的連接關系
3. 內存局部性差：緩存命中率低于數組

適用性分析

• 適合鏈表：歸并排序、插入排序
• 不適合鏈表：堆排序、希爾排序

冒泡排序在鏈表中的實現

算法原理

通過相鄰節點比較和交換完成排序

C++實現

void bubbleSort(ListNode* head) {
    if (!head || !head->next) return;
    
    bool swapped;
    ListNode* ptr1;
    ListNode* lptr = nullptr;
    
    do {
        swapped = false;
        ptr1 = head;
        
        while (ptr1->next != lptr) {
            if (ptr1->val > ptr1->next->val) {
                swap(ptr1->val, ptr1->next->val);
                swapped = true;
            }
            ptr1 = ptr1->next;
        }
        lptr = ptr1;
    } while (swapped);
}

復雜度分析

• 時間復雜度：O(n2)
• 空間復雜度：O(1)

選擇排序在鏈表中的實現

算法原理

每次選擇未排序部分的最小值放到已排序序列末尾

C++實現

void selectionSort(ListNode* head) {
    ListNode* current = head;
    
    while (current) {
        ListNode* min = current;
        ListNode* temp = current->next;
        
        while (temp) {
            if (temp->val < min->val)
                min = temp;
            temp = temp->next;
        }
        
        swap(current->val, min->val);
        current = current->next;
    }
}

復雜度分析

• 時間復雜度：O(n2)
• 空間復雜度：O(1)

插入排序在鏈表中的實現

算法原理

構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置插入

C++實現

ListNode* insertionSort(ListNode* head) {
    if (!head || !head->next) return head;
    
    ListNode* dummy = new ListNode(0);
    ListNode* prev = dummy;
    ListNode* curr = head;
    
    while (curr) {
        ListNode* next = curr->next;
        
        while (prev->next && prev->next->val < curr->val)
            prev = prev->next;
            
        curr->next = prev->next;
        prev->next = curr;
        prev = dummy;
        curr = next;
    }
    
    return dummy->next;
}

復雜度分析

• 時間復雜度：O(n2)
• 空間復雜度：O(1)

歸并排序在鏈表中的實現

算法原理

分治法：分割鏈表→排序子鏈表→合并有序鏈表

C++實現

// 分割鏈表
ListNode* split(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head->next;
    
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    ListNode* mid = slow->next;
    slow->next = nullptr;
    return mid;
}

// 合并有序鏈表
ListNode* merge(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    
    while (l1 && l2) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

// 歸并排序主函數
ListNode* mergeSort(ListNode* head) {
    if (!head || !head->next) return head;
    
    ListNode* mid = split(head);
    ListNode* left = mergeSort(head);
    ListNode* right = mergeSort(mid);
    
    return merge(left, right);
}

復雜度分析

• 時間復雜度：O(n log n)
• 空間復雜度：O(log n)（遞歸?？臻g）

快速排序在鏈表中的實現

算法原理

選擇基準→分區→遞歸排序

C++實現

ListNode* partition(ListNode* head, ListNode* end, ListNode** newHead, ListNode** newEnd) {
    ListNode* pivot = end;
    ListNode* prev = nullptr;
    ListNode* curr = head;
    ListNode* tail = pivot;
    
    while (curr != pivot) {
        if (curr->val < pivot->val) {
            if (!(*newHead)) *newHead = curr;
            prev = curr;
            curr = curr->next;
        } else {
            if (prev) prev->next = curr->next;
            ListNode* temp = curr->next;
            curr->next = nullptr;
            tail->next = curr;
            tail = curr;
            curr = temp;
        }
    }
    
    if (!(*newHead)) *newHead = pivot;
    *newEnd = tail;
    return pivot;
}

ListNode* quickSortRecur(ListNode* head, ListNode* end) {
    if (!head || head == end) return head;
    
    ListNode* newHead = nullptr;
    ListNode* newEnd = nullptr;
    
    ListNode* pivot = partition(head, end, &newHead, &newEnd);
    
    if (newHead != pivot) {
        ListNode* temp = newHead;
        while (temp->next != pivot) temp = temp->next;
        temp->next = nullptr;
        
        newHead = quickSortRecur(newHead, temp);
        temp = getTail(newHead);
        temp->next = pivot;
    }
    
    pivot->next = quickSortRecur(pivot->next, newEnd);
    return newHead;
}

ListNode* quickSort(ListNode* head) {
    return quickSortRecur(head, getTail(head));
}

復雜度分析

• 時間復雜度：平均O(n log n)，最壞O(n2)
• 空間復雜度：O(log n)

性能比較與算法選擇

實驗數據對比

選擇建議

1. 小規模數據：插入排序（實現簡單）
2. 通用場景：歸并排序（穩定高效）
3. 內存敏感：快速排序（遞歸深度?。?/li>

實際應用案例

場景：學生成績管理系統

struct Student {
    int id;
    string name;
    float score;
    Student* next;
};

void sortByScore(Student* head) {
    // 使用歸并排序按成績降序排列
    auto cmp = [](Student* a, Student* b) {
        return a->score > b->score;
    };
    // ...實現基于比較器的歸并排序
}

總結

本文詳細探討了五種主流排序算法在C++鏈表中的實現方法。通過對比分析可以得出： 1. 歸并排序是鏈表排序的最佳通用選擇 2. 插入排序適合近乎有序的鏈表或小規模數據 3. 快速排序在平均情況下表現良好但存在最壞情況 4. 冒泡和選擇排序僅適用于教學演示

參考文獻

1. 《算法導論》第三版 - Thomas H. Cormen
2. 《數據結構與算法分析》 - Mark Allen Weiss
3. C++標準模板庫(STL)文檔
4. LeetCode鏈表相關問題集

”`