归并排序 | Juchia

图示

分治思想
栈内视图
过程视图
平面视图

原理

Code

1
2
3

1. 尽可能的一组数据拆分成两个元素个数相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是 1 为止。
2. 将相邻的两个子组进行合并，合并同时对这两个子组排序，变成一个有序的大组
3. 不断的重复步骤2，直到终只有一个组为止，

实现

java

public static void _排序(Comparable[] a) {
    _临时数组 = new Comparable[a.length];

    _拆分(a,0,a.length-1);
}

public static void _拆分(Comparable[] a,int _开始, int _结束) {

    // 如上一次为 0 1 2
    // 开始为 0
    // 结束为 2

    // 中位数 = (0+2)/2 = 1
    // 左边组 开始0 结束1
    // 右边组 开始2 结束2
    // 此时 右边组 开始 = 结束, 不用再拆分成两组了
    if(_结束 <= _开始){
        return;
    }

    int _中位数 = (_开始 + _结束) / 2;

    _拆分(a, _开始, _中位数);

    _拆分(a, _中位数+1, _结束);

    _比较并合并(a, _开始, _中位数, _结束);
}

public static void _比较并合并(Comparable[] a, int _开始, int _中位数, int _结束) {


    // 比如 0 1 2 3 4 5 6 7 8 9
    // 中位数 (0+9)/2 = 4;
    // 开始索引 0
    // 结束索引 9
    // 0 1 2 3 4 为一组
    // 5 6 7 8 9 为一组

    int _插入临时数组索引 = _开始;

    int _左边组遍历索引 = _开始;
    int _右边组遍历索引 = _中位数+1;


    //找出两组中的小元素, 存到临时数组
    while (_左边组遍历索引<=_中位数 && _右边组遍历索引<=_结束) {

        if(_是否小于(a[_左边组遍历索引], a[_右边组遍历索引])){
            _临时数组[_插入临时数组索引] = a[_左边组遍历索引];
            _左边组遍历索引++;
        }else {
            _临时数组[_插入临时数组索引] = a[_右边组遍历索引];
            _右边组遍历索引++;
        }
        _插入临时数组索引++;
    }

    // 右边组已经比完了, 左边组还有数, 不用比了, 直接将剩下的元素放到后面空的几个位置
    while(_左边组遍历索引<=_中位数){
        _临时数组[_插入临时数组索引] = a[_左边组遍历索引];
        _左边组遍历索引++;
        _插入临时数组索引++;
    }

    //左边组已经比完了, 右边组还有数, 不用比了, 直接将剩下的元素放到后面空的几个位置
    while(_右边组遍历索引<=_结束){
        _临时数组[_插入临时数组索引] = a[_右边组遍历索引];
        _右边组遍历索引++;
        _插入临时数组索引++;
    }

    //将这两组合并且排好序的元素从临时数组复制到原数组
    for (int i = _开始; i <=_结束 ; i++) {
        a[i] = _临时数组[i];
    }

}

性能

Code

如果一个数组有8个元素，那么它将每次除以2找小的子数组，共拆log2(8)次，即3次
所以树共有3层，那么自顶(k=0)向下第k层有2^k个子数组
每个子数组的长度为2^(3-k)，每个子数组最多需要2^(3-k)次比较。
因此每层的比较次数为 子数组数*每个子数组需要的比较次数 即 2^k * 2^(3-k) = 2^3
那么3层总共为 3 * 2^3 次比较。

如果一个数组有n个元素，那么它将每次除以2找小的子数组，共拆log2(n)次
所以树共有log2(n)层，那么自顶(k=0)向下第k层有2^k个子数组
每个子数组的长度为2^(log2(n)-k)，每个子数组最多需要2^(log2(n)-k)次比较。
因此每层的比较次数为 子数组数*每个子数组需要的比较次数 即 2^k * 2^(log2(n)-k) = 2^log2(n)
那么log2(n)层总共为 log2(n) * 2^log2(n) = log2(n) * n 次比较。

根据大O推导法则，忽略底数，最终归并排序的时间复杂度为O(nlogn);

稳定性

稳定