連結列表合併排序

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