链接列表合并排序
在本教程中，我们将学习如何使用合并排序算法对链接列表进行排序。它是对链表进行排序的最优选算法之一，因为缓慢的指针随机访问使其他算法的性能变差（例如：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