链接列表合并排序

Harshit Jindal 2023年1月30日 2021年3月21日
  1. 链表合并排序算法
  2. 链表合并排序图
  3. 链表合并排序实现
  4. 链表合并排序算法的复杂度
链接列表合并排序

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

链表合并排序算法

head 成为要排序的链表的第一个节点。

mergeSort(head)

  • 如果链接列表为空或节点为 1,则说明该列表已排序。按原样返回链接列表。
  • 使用 getMid() 函数获取 mid 节点及其上一个节点 prev
  • prev->next 设置为 NULL,可以将链表分成两个相等的部分。
  • 递归调用 mergeSort(head)mergeSort(mid) 对两个较小的链表进行排序。
  • 使用 merge(head, mid) 功能合并两个排序的链表。

getMid(head)

我们使用两个指针,一个为 slow,另一个为 fastfast 指针以 slow 的两倍速度覆盖链接列表,当 fast 节点落在链接列表的末端时,slow 指针落在 mid 节点。我们还使用一个 prev 节点来处理 MergeSort() 函数中的链接列表的拆分。

  • mid 初始化为 head,将 fast 初始化为 head,将 prev 初始化为 NULL
  • fast!=NULLfast->next!=NULL 的同时,执行以下操作:
    • prev=mid,在中点到拆分列表之前存储对指针的引用。
    • mid=mid->next,每次迭代以 1 个节点的速度移动到中间。
    • fast=fast->next->next,将 fastmid 的 2 倍的速度移动。
  • 返回一对包含 prevmid 的节点。

merge(F,B)

F 是链接列表的第一部分的开头,而 B 是链接列表的第二部分的开头。我们合并两个排序的子列表 F 和 B,以获得最终的排序链表。

  • 初始化指向 Ffirst 和指向 Bsecond。同样,用 NULL 初始化 merged 来保存合并的排序列表,并用 tail 来管理排序列表的末尾。
  • 虽然我们没有用完 firstsecond,但请执行以下操作:
    • firstsecond 进行比较以找到较小的元素,并使用它初始化 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 =firsttail=first
    • first 节点向前移动,first=first->next
  • 如果 S 中剩余元素,请执行以下操作:
    • tail 的末尾附加 second,然后将尾巴指针向前移动,tail->next =secondtail=second
    • second 向前移动一个节点,second=second->next
  • tail 的末尾附加 NULL 并返回 merged 排序列表。

链表合并排序图

  • 我们来看看链表 3 -> 2 -> 4 -> 1 -> NULL
  • 我们将其分为两个链接列表:3 -> 2 -> NULL4-> 1->空
  • 我们将 3 -> 2 -> Null 拆分为 3 -> Null2 -> Null,合并它们以获得排序后的子列表 2 -> 3 -> Null
  • 我们将 4 -> 1 -> Null 分成 4 -> Null1 -> Null,将它们合并以获得排序后的子列表 1 -> 4 -> Null
  • 合并 2 -> 3 -> Null1 -> 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 avatar Harshit Jindal avatar

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

相关文章 - Data Structure

相关文章 - Linked List