合并排序

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