單鏈表的冒泡排序實現：從原理到代碼詳解

引言

單鏈表作為一種常見的數據結構，其排序操作因節點無法隨機訪問（需通過指針遍歷）而與數組排序存在差異。冒泡排序因其實現簡單、無需額外空間（僅需指針操作），成為單鏈表排序的常用選擇。本文將詳細解析單鏈表冒泡排序的原理、實現細節、優化點及常見錯誤，幫助讀者徹底掌握這一算法。

一、單鏈表冒泡排序的核心思路

冒泡排序的核心是重復遍歷鏈表，每次比較相鄰節點的值，若順序錯誤則交換，直至整個鏈表有序。針對單鏈表的特點，算法需解決兩個關鍵問題：

1. 如何標記每趟排序的終點（避免重復比較已排好的尾部元素）；
2. 如何檢測鏈表是否已提前有序（減少無效遍歷）。

二、算法關鍵變量解析

在實現代碼中，三個指針變量是核心，需明確其作用：

變量名	作用
pPre	指向當前比較的前一個節點
pCur	指向當前比較的后一個節點（與pPre相鄰）
pTail	標記每趟排序的終點（初始為NULL，每趟排序后指向當前趟的最后一個節點，下一趟排序僅需遍歷到pTail前）

此外，IsChange變量用于標記當前趟是否發生過交換：若未發生交換，說明鏈表已完全有序，可直接退出排序，避免后續無效操作。

三、代碼實現與詳細注釋

// 單鏈表冒泡排序函數（升序）
// plist為鏈表頭指針
void BubbleSort(pList plist) {  pNode pCur = NULL;    // 當前節點指針pNode pPre = NULL;    // 當前節點的前一個節點指針pNode pTail = NULL;   // 每趟排序的終點指針（初始為NULL，即鏈表末尾）// 邊界條件：空鏈表或只有一個節點，無需排序if (plist == NULL || plist->next == NULL) {  return;  }// 外層循環：控制排序趟數（每趟將最大元素"冒泡"到尾部）// 當plist == pTail時，說明所有元素已排序完成while (plist != pTail) {  int IsChange = 0;  // 標記當前趟是否發生交換（0：未交換，1：已交換）pPre = plist;      // 每趟開始時，pPre從鏈表頭出發pCur = pPre->next; // pCur指向pPre的下一個節點// 內層循環：控制每趟的比較次數（遍歷到pTail前）while (pCur != pTail) {  // 若前一個節點值大于后一個節點值，交換數據（升序排序）if (pPre->data > pCur->data) {  // 修正原代碼的交換錯誤：正確的交換邏輯int tmp = pPre->data;  pPre->data = pCur->data;  pCur->data = tmp;  IsChange = 1;  // 標記發生交換}// 移動指針，繼續比較下一對相鄰節點pPre = pPre->next;  pCur = pCur->next;  }// 若當前趟未發生交換，說明鏈表已完全有序，直接退出if (!IsChange) {  return;  }// 更新pTail為當前趟的最后一個節點（下一趟無需比較到此節點）pTail = pPre;  }
}

四、關鍵邏輯詳解

1. 為什么需要pTail？

在數組冒泡排序中，每趟排序后最大元素會 “浮” 到末尾，下一趟可減少一次比較。單鏈表中，pTail的作用類似：每趟排序后，pTail指向當前趟的最后一個節點（即該趟確定的最大元素），下一趟只需遍歷到pTail之前，減少無效比較次數，優化效率。

2. IsChange的作用是什么？

若某趟排序中未發生任何交換（IsChange=0），說明鏈表已完全有序，可直接退出排序。例如，初始鏈表為1->2->3->4，第一趟遍歷后IsChange=0，算法直接返回，避免后續n-1趟的無效遍歷，最佳情況下時間復雜度可優化至 O (n)。

五、時間復雜度與空間復雜度

• 時間復雜度：
  • 最壞情況（鏈表逆序）：需n-1趟，每趟比較n-i次，總復雜度為O(n2)；
  • 最好情況（鏈表已有序）：僅需 1 趟比較，復雜度為O(n)。
• 空間復雜度：僅使用常數個指針變量（pCur、pPre、pTail等），復雜度為O(1)。

六、示例演示

以初始鏈表3->1->4->2為例，演示排序過程：

1. 第一趟排序：
   • 初始pTail=NULL，pPre=3，pCur=1；
   • 比較3>1：交換后鏈表為1->3->4->2，IsChange=1；
   • 移動指針：pPre=3，pCur=4（3<4，不交換）；
   • 繼續移動：pPre=4，pCur=2（4>2，交換后鏈表為1->3->2->4，IsChange=1）；
   • 第一趟結束，pTail=4（指向當前最大元素 4）。
2. 第二趟排序：
   • pTail=4，遍歷至pCur!=4；
   • pPre=1，pCur=3（1<3，不交換）；
   • pPre=3，pCur=2（3>2，交換后鏈表為1->2->3->4，IsChange=1）；
   • 第二趟結束，pTail=3。
3. 第三趟排序：
   • pTail=3，遍歷至pCur!=3；
   • pPre=1，pCur=2（1<2，不交換）；
   • 遍歷結束，IsChange=0，算法直接返回。

最終鏈表為1->2->3->4，排序完成。

七、總結

單鏈表的冒泡排序通過指針操作實現，核心在于利用pTail減少無效比較、利用IsChange檢測提前有序，從而優化效率。需注意指針移動邏輯和數據交換的正確性，避免因細節錯誤導致排序失敗。

該算法實現簡單、空間開銷小，適合小規模鏈表排序；若需處理大規模數據，可考慮單鏈表的快速排序等更高效算法。