連結列表合併排序
在本教程中，我們將學習如何使用合併排序演算法對連結列表進行排序。它是對連結串列進行排序的最優選演算法之一，因為緩慢的指標隨機訪問使其他演算法的效能變差（例如：quicksort 和 heapsort）。
連結串列合併排序演算法
讓 head 成為要排序的連結串列的第一個節點。
mergeSort(head)
-
如果連結列表為空或節點為
1，則說明該列表已排序。按原樣返回連結列表。 -
使用
getMid()函式獲取mid節點及其上一個節點prev。 -
將
prev->next設定為NULL，可以將連結串列分成兩個相等的部分。 -
遞迴呼叫
mergeSort(head)和mergeSort(mid)對兩個較小的連結串列進行排序。 -
使用
merge(head, mid)功能合併兩個排序的連結串列。
getMid(head)
我們使用兩個指標，一個為 slow，另一個為 fast，fast 指標以 slow 的兩倍速度覆蓋連結列表，當 fast 節點落在連結列表的末端時，slow 指標落在 mid 節點。我們還使用一個 prev 節點來處理 MergeSort() 函式中的連結列表的拆分。
-
將
mid初始化為head，將fast初始化為head，將prev初始化為NULL。 -
在
fast！=NULL和fast->next！=NULL的同時，執行以下操作：prev=mid，在中點到拆分列表之前儲存對指標的引用。mid=mid->next，每次迭代以1個節點的速度移動到中間。fast=fast->next->next，將fast以mid的 2 倍的速度移動。
-
返回一對包含
prev和mid的節點。
merge(F,B)
F 是連結列表的第一部分的開頭，而 B 是連結列表的第二部分的開頭。我們合併兩個排序的子列表 F 和 B，以獲得最終的排序連結串列。
-
初始化指向
F的first和指向B的second。同樣，用NULL初始化merged來儲存合併的排序列表，並用tail來管理排序列表的末尾。 -
雖然我們沒有用完
first或second，但請執行以下操作：-
將
first與second進行比較以找到較小的元素，並使用它初始化insertedNode。
```c++
if (first->data<second->data) {
insertedNode=first;
first=first->next;
}else { `insertedNode` = `second`; `second` = `second->next`; } ``` -
如果
merged為空，則用tail將其初始化。 -
在尾巴的末尾附加
insertedNode，並將tail指標向前移動。`tail->next` = `insertedNode` `tail` = `insertedNode`
-
-
如果
F中剩餘元素，請執行以下操作：- 將
first附加到tail的末端，然後將尾巴指標向前移動，tail->next=first，tail=first。 - 將
first節點向前移動，first=first->next。
- 將
-
如果
S中剩餘元素，請執行以下操作：- 在
tail的末尾附加second，然後將尾巴指標向前移動，tail->next=second，tail=second。 - 將
second向前移動一個節點，second=second->next。
- 在
-
在
tail的末尾附加NULL並返回merged排序列表。
連結串列合併排序圖
-
我們來看看連結串列
3 -> 2 -> 4 -> 1 -> NULL -
我們將其分為兩個連結列表：
3 -> 2 -> NULL和4-> 1->空 -
我們將
3 -> 2 -> Null拆分為3 -> Null和2 -> Null，合併它們以獲得排序後的子列表2 -> 3 -> Null -
我們將
4 -> 1 -> Null分成4 -> Null和1 -> Null，將它們合併以獲得排序後的子列表1 -> 4 -> Null -
合併
2 -> 3 -> Null和1 -> 4 -> Null以獲得排序後的連結列表為1 -> 2 -> 3 -> 4 -> Null。
連結串列合併排序實現
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; Node(int x) { this->data = x; this->next = NULL; } }; pair<Node*, Node*> getMid(Node* head) { Node* mid = head; Node* fast = head; Node* prev = NULL; while (fast != NULL && fast->next != NULL) { prev = mid; mid = mid->next; fast = fast->next->next; } pair<Node*, Node*> result(prev, mid); return result; } Node* merge(Node* F, Node* B) { Node* first = F; Node* second = B; Node* merged = NULL; Node* tail = NULL; while ((first != NULL) && (second != NULL)) { Node* insertedNode = NULL; if (first->data < second->data) { insertedNode = first; first = first->next; } else { insertedNode = second; second = second->next; } if (merged) { tail->next = insertedNode; tail = insertedNode; } else { merged = tail = insertedNode; } } while (first != NULL) { tail->next = first; tail = first; first = first->next; } while (second != NULL) { tail->next = second; tail = second; second = second->next; } if (tail) { tail->next = NULL; } return merged; } void mergeSort(Node*& head) { if ((head == NULL) || (head->next == NULL)) { return; } pair<Node*, Node*> a = getMid(head); Node* prev = a.first; Node* mid = a.second; if (prev) { prev->next = NULL; } mergeSort(head); mergeSort(mid); head = merge(head, mid); } void printList(Node* head) { Node* curr = head; while (curr != NULL) { cout << curr->data << " "; curr = curr->next; } cout << "\n"; } int main() { Node* head = new Node(5); head->next = new Node(6); head->next->next = new Node(4); head->next->next->next = new Node(3); head->next->next->next->next = new Node(2); head->next->next->next->next->next = new Node(1); printList(head); mergeSort(head); printList(head); return 0; } 連結串列合併排序演算法的複雜度
時間複雜度
- 平均情況
合併排序是一種遞迴演算法。下面的遞迴關係給出了 Merge 排序的時間複雜度表示式。
T(n) = 2T(n/2) + θ(n) 該遞迴關係的結果為 T(n) = nLogn。我們還可以將其視為大小為 n 的連結列表，該列表被劃分為最多 Logn 部分。排序每個部分併合並每個部分需要 O(n) 時間。
因此，時間複雜度約為[大 Theta]：O(nlogn)。
- 最壞情況
最壞情況下的時間複雜度是 [Big O]：O(nlogn)。它與平均情況下的時間複雜度相同。
- 最佳情況
最佳情況下的時間複雜度是 [Big Omega]：O(nlogn)。它與最壞情況下的時間複雜度相同。但是，如果已對連結串列進行排序，則可以將時間複雜度降低為 O(n)。
空間複雜度
由於堆疊中遞迴呼叫佔用的空間，因此連結串列上的合併排序演算法的空間複雜度為 O(logn)。如果我們忽略遞迴呼叫佔用的空間，則空間複雜度可以視為 O(1)。
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn