二路归并排序及时间复杂度分析

创作时间:

作者:

@小白创作中心

二路归并排序及时间复杂度分析

引用

CSDN

https://blog.csdn.net/weixin_44870613/article/details/128935283

二路归并排序是一种高效的递归排序算法，其时间复杂度为O(nlogn)。本文将详细介绍二路归并排序的原理、实现代码以及时间复杂度分析，帮助读者深入理解这一经典算法。

序言

二路归并排序是一种效率极高的递归排序，将数组A化为有序数组时间复杂度为O(nlogn)。

思想

二路归并排序分为拆分数组以及合并两个操作。

切分（自上而下）时间复杂度2*T(n/2)

每次从数组A中间切分，将数组分为[low，mid]以及[mid+1，high]两段，直至不可再分(low不小于high)即最终分成最下层一个一个的数组。当然在代码中不会让他真的变成一个一个数组！用下标圈定范围即可。

合并（自下而上）时间复杂度T(n)

将两段各自有序的数组合并成一个有序数组，并逐步向上合并，最终得到一个有序数组。

下面举例分析如何进行合并操作，需要三个指针，我设为i，j，k

比较下面两个数组指针（i，j）所指位置的数值
将较小的放入上面的有序数组里，例如第一次比较17<28，故将17放入上面有序数组中的第一个位置。此时i++，k++即i，k向后移动一位
直至下面两个数组其中之一遍历完成，该例子为【17，24】遍历完成，而【28，40】并未遍历完成
最终将未遍历完的数组剩下部分复制到上面的那个有序数组里

辅助数组B的作用
在合并操作中，先将此次需要合并的A数组全部放入B中，即i，j所指向的数组B，没错，他俩实际上在代码中就是一个数组只不过人为的在中间分开了，分为[low，mid]，[mid+1，high]两段而已。

再经历上述合并步骤，将这两段数组合并到A数组的原位置中[low，high]中。

即i，j指向的是B数组的元素，而k指向的是A数组的元素

代码

#include<iostream>
using namespace std;
#define n 16
//辅助数组--->空间复杂度O(n)
int* B = (int*)malloc((n + 1) * sizeof(int));
//合并
void merge(int A[], int low, int mid, int high) {
    //将A复制到B
    for (int k = low; k <= high; k++) {
        B[k] = A[k];
    }
    int i, j, k;
    //循环结束条件需要满足左右数组其中之一遍历结束
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
        if (B[i] <= B[j])
            A[k] = B[i++];
        else
            A[k] = B[j++];
    }
    //若左数组未遍历结束
    while (i <= mid)A[k++] = B[i++];
    //若右半数组未遍历结束
    while (j <= high)A[k++] = B[j++];
}
//二路归并排序
void mergeSort(int A[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        //左半数组--->T(n/2)
        mergeSort(A, low, mid);
        //右半数组--->T(n/2)
        mergeSort(A, mid + 1, high);
        //合并--->T(n)
        merge(A, low,mid, high);
    }
}
int main() {
    int A[16] = {24,17,40,28,13,14,22,32,40,21,48,4,47,8,37,18};
    mergeSort(A, 0, 15);
    for(int i  =0;i<n;i++)
        cout << A[i]<<" ";
    return 0;
}