連結列表合併排序
在本教程中，我們將學習如何使用合併排序演算法對連結列表進行排序。它是對連結串列進行排序的最優選演算法之一，因為緩慢的指標隨機訪問使其他演算法的效能變差（例如：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