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