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