合併排序

Harshit Jindal 2023年1月30日 2021年2月7日
  1. 合併排序演算法
  2. 合併排序示例
  3. 合併排序演算法的實現
  4. 合併排序演算法的複雜度
合併排序

合併排序是最流行、最高效的排序演算法之一。它是基於分治演算法的原理。它的工作原理是將陣列反覆分成兩半,直到我們將陣列分成單個元素。單元素本身就是一個排序的陣列。合併排序將這些小的排序陣列反覆合併,產生更大的排序子陣列,直到我們得到一個最終的排序陣列。它被廣泛應用於電子商務應用中。

合併排序演算法

自上而下的合併排序方法從全陣列的頂部開始,向下遞迴到單個元素。

假設我們有一個未排序的陣列 A[],包含 n 元素。

MergeSort()

  • 取兩個變數 beg & end,然後儲存起始元素和結束元素的索引。
  • 利用公式 mid =(beg+end)/2 找到陣列的中間點,將陣列分成兩半。
  • 將陣列分成兩部分 arr[beg, .... , mid]arr[mid+1, .... , end]
  • 利用遞迴將陣列反覆劃分成單元素的子陣列。
  • 呼叫 merge 函式開始構建排序陣列。

Merge()

  • 初始化輔助陣列 output 來儲存排序後的輸出。
  • 初始化 3 個指標 ijk

    i 指向第一個子陣列 beg 的開始。
    j 指向第二個子陣列 mid+1 的開始。
    kbeg 初始化,保持排序陣列 output 的當前索引。

  • 直到到達 arr[beg, .... ,mid]arr[mid+1, .... ,end] 子陣列的末尾,我們在索引 i&j 的元素中挑出一個較小的值,插入到 output 中。
  • 當其中一個陣列用完後,挑選剩餘的元素插入 output 中。
  • output 複製到 arr[beg, ... , end] 中。

合併排序示例

假設我們有陣列:(5,3,4,2,1,6)。我們將使用合併排序演算法對其進行排序。

操作 (5,3,4,2,1,6) mergesort(0,5)
divide (5,3,4) (2,1,6) mergesort(0,2) mergesort(3,5)
divide (5,3) (4) (2,1) (6) mergesort(0,1) mergesort(2,2) mergesort(3,4) mergesort(5,5)
divide (5) (3) (4) (2) (1) (6) 陣列分解為單個元素
merge (3,5) (4) (1,2) (6) merge(0,1) merge(2,2) merge(3,4) merge(5,5)
merge (3,4,5) (1,2,6) merge(0,2) merge(3,5)
merge (1,2,3,4,5,6) merge(0,5)

我們得到排序的陣列 - (1 2 3 4 5 6)

合併排序演算法的實現

#include<iostream>
using namespace std;

void merge(int arr[], int beg, int mid, int end) {
    int output[end - beg + 1];
    int i = beg, j = mid + 1, k = 0;
    // add smaller of both elements to the output
    while (i <= mid && j <= end) {
        if (arr[i] <= arr[j]) {
            output[k] = arr[i];
            k += 1; i += 1;
        }
        else {
            output[k] = arr[j];
            k += 1; j += 1;
        }
    }
    // remaining elements from first array
    while (i <= mid) {
        output[k] = arr[i];
        k += 1; i += 1;
    }
    // remaining elements from the second array
    while (j <= end) {
        output[k] = arr[j];
        k += 1; j += 1;
    }
    // copy output to the original array
    for (i = beg; i <= end; i += 1) {
        arr[i] = output[i - beg];
    }
    }

    void mergeSort(int arr[], int beg, int end) {

    if (beg < end) {
        int mid = (beg + end) / 2;
        //divide and conquer
        mergeSort(arr, beg, mid);    // divide : first half
        mergeSort(arr, mid + 1, end);  // divide: second half
        merge(arr, beg, mid, end);   // conquer
    }
    }
    int main() {

    int n = 6;
    int arr[6] = {5, 3, 4, 2, 1, 6};
    cout << "Input array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    mergeSort(arr, 0, n - 1); // Sort elements in ascending order
    cout << "Output array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
}

合併排序演算法的複雜度

時間複雜度

  • 平均情況

合併排序是一種遞迴演算法。下面的遞迴關係給出了合併排序的時間複雜度表示式。

T(n) = 2T(n/2) + θ(n)

這個遞迴關係的結果給出了 T(n)=nLogn.我們也可以把它看作是一個大小為 n 的陣列被分成最多的 Logn 部分,每一部分的合併需要 O(n) 時間。

因此,時間複雜度是 [Big Theta]:O(nLogn)

  • 最壞情況

最壞情況下的時間複雜度為[大 O]:O(nLogn)

  • 最佳情況

最佳情況下的時間複雜度是 [Big Omega]:O(nLogn)。它與最壞情況下的時間複雜度相同。

空間複雜度

合併排序演算法的空間複雜度為 O(n),因為在輔助陣列中儲存排序子陣列需要 n 個輔助空間。

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

相關文章 - Sort Algorithm