迹忆客 专注技术分享

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

链表合并排序图

• 我们来看看链表 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)。