数据结构-排序（八）归并排序

一、算法思想

归并： 将两个或两个以上的有序表组合成一个新有序表

2路归并排序：

排序过程

1. 初始序列看成n个有序子序列，每个子序列长度为1
2. 两两合并，得到 ⌊ n / 2 ⌋ 个长度为2或1的有序子序列
3. 再两两合并，重复直至得到一个长度为n的有序序列为止

以上gif动图制作，图像来自网站：VisuAlgo

二、代码实现

#include <iostream>
#include <string>
using namespace std;
int *b; //辅助数组
/**
 * 归并操作
 * @param arr 
 * @param low 
 * @param mid 
 * @param high 
 */
void Merge(int arr[], int low, int mid, int high) {
    int i, j, k;
    for (k = low; k <= high; k++) { //讲arr数组复制到b数组
        b[k] = arr[k];
    }
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
        if (b[i] <= b[j]) { //将较小值赋值到A中
            arr[k] = b[i++];
        }else {
            arr[k] = b[j++];
        }
    }//for
    while (i <= mid) {
        arr[k++] = b[i++];
    }
    while (j <= high) {
        arr[k++] = b[j++];
    }
}

/**
 * 归并排序
 * @param arr 
 * @param low 
 * @param high 
 */
void MergeSort(int arr[], int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2; //中间划分
            MergeSort(arr, low, mid);           //左半部分归并排序
            MergeSort(arr, mid + 1, high); //右半部分归并排序
            Merge(arr, low, mid, high); //归并
        }
}
/**
 * 输出数组
 * @param arr
 * @param n
 */
void PrintArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << "  ";
    }
    printf("\n");
}
int main() {
    int arr[] = {12, 28, 20, 50, 48, 1, 5, 28};
    int n = sizeof(arr) / sizeof(arr[0]);
    b = (int *)malloc(n * sizeof(int)); //辅助数组
    cout << "输出arr初始数组" << endl;
    PrintArray(arr, n);
    cout << "arr堆排序" << endl;
    MergeSort(arr,0, n - 1 );
    cout << "输出arr排序后数组" << endl;
    PrintArray(arr, n);
    return 0;
}

三、算法效率分析

⼆叉树的第h层最多有 $2^{h-1}$个结点；若树高为h，则应满足 $n\le2^{h-1}$ 即 $h - 1 = ⌈ log_2n ⌉$

结论： n个元素进⾏2路归并排序，归并趟数为$⌈ log_2n ⌉$

1、每趟归并时间复杂度为 O(n)，则算法时间复杂度为$O(nlong_2n)$

2、空间复杂度为O(n)，来自于辅助数组B

3、稳定性：稳定