简介

归并排序是一种使用分治策略的排序算法,相比于之前介绍的插入排序算法,分治算法在数据量较大的场景中速度要快很多(在本文最后会比价两个算法的优劣)

算法原理简述

合并两个已经排好序的数组

首先想象一下你的面前摆放着两堆自上而下已经从大倒小排好序的扑克牌, 你现在要把这两堆扑克牌按照从大到小的顺序合并成一堆, 你需要先拿起牌堆一和牌堆二顶上的一张牌, 然后对比大小, 把小的哪一张放到手中, 大的哪一张放回到原来的牌堆, 重复上面的步骤, 直到其中一堆牌全部被放到手上后, 把另一堆牌堆的所有牌依次追加到手中(说的有点繁琐, 最好能自己按照上面的步骤试一下, 能够更快的理解).

图解

C++ 代码

// 合并两个排好序的子数组
// A: 处理的数组
// p: 子数组的起始
// q: 子数组的中点
// r: 子数组的结尾
void merge(int * A,int p, int q, int r){
    
    // 获取左边子数组的长度
    int n1 = q - p + 1;

    // 获取右边子数组的长度
    int n2 = r - q;
    
    // 创建一个新的数组保存左边的子数组
    int * L = new int[n1];
    
    // 创建一个新的数组保存右边的子数组
    int * R = new int[n2];
    
    // 保存左边的子数组到数组 L
    for(int i = 0; i<n1; i++){
        L[i] = A[p+i];
    }
    
    // 保存右边的子数组到数组 R
    for(int j =0; j<n2; j++){
        R[j] = A[q+j+1];
    }

    // 记录数组 L 和 R 被取出元素的数量
    // 防止数组越界
    int L_sum = 0;
    int R_sum = 0;

    // 将 L 和 R 排序保存到主数组中
    for(int k=p; k<=r; k++){

        // 如果左边数组 (L) 的当前元素 < 右边数组 (R) 的当前元素
        // 并且左边的数组还没有越过边界
        // 则将 (L) 的当前元素追加到子数组中
        if(L[L_sum] < R[R_sum] && L_sum < n1){
            A[k] = L[L_sum];
            L_sum++;
        }
        // 如果右边数组 (R) 还没有越界
        // 则将 (R) 的当前元素追加到子数组中
        else if(R_sum < n2){
            A[k] = R[R_sum];
            R_sum++;
        }
        // 否则将数组 (L) 追加到子数组中
        else{
            A[k] = L[L_sum];
            L_sum++;
        }
    }
}

伪码

MERGE(A, p, q, r)
    n1 = q - p + 1
    n2 = r - q
    let L[1..n1 + 1] and R[1..n2 + 1] be new arrays
    for i = 1 to n1
        L[i] = A[p + i - 1]
    for j = 1 to n2
        L[j] = A[q + j]

    // 添加哨兵, 防止数组越界
    L[n1 + 1] = MAX
    L[n2 + 1] = MAX

    i = 1
    j = 1
    
    for k = p to r
        if L[i] <= R[j]
            A[k] = L[i]
            i = i + 1
        else A[k] = R[j]
            j = j + 1

分解大数组为小数组并递归的求解他们

一般环境下除了合并两个排好序的数组之外更多的是排序一个无序的数组,这里聊一下怎么利用上面的那个算法来处理排序一个无序数组(语言表达能力不好,直接看图吧, 方便起见, 这里使用 2³ 个数据为例)

图解

C++ 代码

// 分解一个大的数组
// A: 数组
// p: 子数组的起始
// r: 子数组的结尾
void merge_sort(int * A,int p, int r){
   
    // 当子数组为 1 的时候停止递归
    if(p < r){
        // 得到当前子数组的中点
        int q = floor((p+r)/2);

        // 递归的去分解前半段子数组
        merge_sort(A, p, q);

        // 递归的去分解后半段子数组
        merge_sort(A, q+1, r);
        
        // 将子数组合并
        merge(A, p, q, r);
    }
}

伪码

MERGE-SORT(A, p, q)
    if p < r
        q = ⌊(p + r) / 2⌋
        MERGE-SORT(A, p, q)
        MERGE-SORT(A, q + 1, r)
        MERGE(A, p, q, r)

完整归并排序 C++ 代码

/*************************************************************************
> File Name: sf2.cpp
> Author: 
> Mail: 
> Created Time: 2018年06月05日 星期二 00时01分49秒
************************************************************************/
#include<iostream>
#include<math.h>
using namespace std;


// 合并两个排好序的数组
void merge(int * A,int p, int q, int r);

// 分解一个大的数组
void merge_sort(int * A,int p, int r);

int main(){

    // 测试数据
    int A[9] = {10,9,8,6,5,3,1,2,4};
    
    // 数组的起始 
    int p = 0;
    // 数组的结尾
    int r = 8;

    // 打印测试数据
    cout << "测试数据: ";
    for(int i = 0; i<=r; i++){
        cout << A[i] << " ";
    }
    cout << endl;

    // 排序入口
    merge_sort(A, p, r);

    // 打印运行结果
    cout << "运行结果: ";
    for(int i = 0; i<=r; i++){
        cout << A[i] << " ";
    }
    return 0;
}

// 合并两个排好序的子数组
// A: 处理的数组
// p: 子数组的起始
// q: 子数组的中点
// r: 子数组的结尾
void merge(int * A,int p, int q, int r){
    
    // 获取左边子数组的长度
    int n1 = q - p + 1;

    // 获取右边子数组的长度
    int n2 = r - q;
    
    // 创建一个新的数组保存左边的子数组
    int * L = new int[n1];
    
    // 创建一个新的数组保存右边的子数组
    int * R = new int[n2];
    
    // 保存左边的子数组到数组 L
    for(int i = 0; i<n1; i++){
        L[i] = A[p+i];
    }
    
    // 保存右边的子数组到数组 R
    for(int j =0; j<n2; j++){
        R[j] = A[q+j+1];
    }

    // 记录数组 L 和 R 被取出元素的数量
    // 防止数组越界
    int L_sum = 0;
    int R_sum = 0;

    // 将 L 和 R 排序保存到主数组中
    for(int k=p; k<=r; k++){

        // 如果左边数组 (L) 的当前元素 < 右边数组 (R) 的当前元素
        // 并且左边的数组还没有越过边界
        // 则将 (L) 的当前元素追加到子数组中
        if(L[L_sum] < R[R_sum] && L_sum < n1){
            A[k] = L[L_sum];
            L_sum++;
        }
        // 如果右边数组 (R) 还没有越界
        // 则将 (R) 的当前元素追加到子数组中
        else if(R_sum < n2){
            A[k] = R[R_sum];
            R_sum++;
        }
        // 否则将数组 (L) 追加到子数组中
        else{
            A[k] = L[L_sum];
            L_sum++;
        }
    }
}

// 分解一个大的数组
// A: 数组
// p: 子数组的起始
// r: 子数组的结尾
void merge_sort(int * A,int p, int r){
   
    // 当子数组为 1 的时候停止递归
    if(p < r){
        // 得到当前子数组的中点
        int q = floor((p+r)/2);

        // 递归的去分解前半段子数组
        merge_sort(A, p, q);

        // 递归的去分解后半段子数组
        merge_sort(A, q+1, r);
        
        // 将子数组合并
        merge(A, p, q, r);
    }
}

简单分析一下归并排序的时间复杂度

方便起见, 这里使用 2^N 个数据为例, 首先我们定义一个变量 N 代表 常量 C 代表分解步骤与处理每个数组元素需要的时间的和(这里可能不是非常准确,但是不妨碍我们求解归并排序算法的最差运行时间, 只是多算了一些分解数组的时间)

下图图示了归并排序的归并树, 每一层的代价为 CN 一共有 log₂N + 1, 所有的代价和为 T(N) = CN log₂N + CN, 使用大 O 记号去掉常量和低阶项得到该算法时间复杂度O(N log₂N)