【基础算法】归并排序

可以参考：35. 排序算法（8）：归并排序的迭代实现 的图解

这里在实现上，把递归与迭代的都贴出来：

首先是递归的实现，比较简单明了

public void digui(int[] a, int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = (right + left) / 2;
    
    // 先把 [left, mid] 和 [mid + 1, right] 两个范围内的子数组分别处理成有序的
    digui(a, left, mid);
    digui(a, mid + 1, right);
    
    // 在把两个有序的数组合并
    int[] tmp = new int[right - left + 1];
    int lS = left;
    int rS = mid + 1;
    int i = 0;
    while (lS <= mid && rS <= right) {
        if (a[lS] <= a[rS]) {
            tmp[i] = a[lS];
            ++lS;
        } else {
            tmp[i] = a[rS];
            ++rS;
        }
        ++i;
    }
    // 后面的两个 while 循环是为了把两两归并的数组中更长的那一段也处理好
    while (lS <= mid) {
        tmp[i] = a[lS];
        ++i;
        ++lS;
    }
    while (rS <= right) {
        tmp[i] = a[rS];
        ++i;
        ++rS;
    }
    System.arraycopy(tmp, 0, a, left, tmp.length);
}

然后是迭代的实现

public static void diedai(int[] a) {
    // 重复使用的辅助数组，提高性能
    int[] tmp = new int[a.length];
    // len 代表每一轮中，需要两两归并的子数组的长度
    // 本质上来说， len 即为 1, 2, 4, 8, 2 的 n 次幂
    int len = 1;
    while (len < a.length) {
        int tmpStart = 0;
        for (int k = 0, maxK = a.length / (len * 2); k < maxK; k++) {
            // 两两归并的数组的第一个数组的起点
            int lS = k * len * 2;
            // 两两归并的数组的第一个数组的终点
            int lE = lS + len - 1;
            // 两两归并的数组的第二个数组的起点
            int rS = lE + 1;
            // 两两归并的数组的第二个数组的终点
            int rE = rS + len - 1;
            // 分段的进行归并
            while (lS <= lE && rS <= rE) {
                if (a[lS] <= a[rS]) {
                    tmp[tmpStart] = a[lS];
                    ++lS;
                } else {
                    tmp[tmpStart] = a[rS];
                    ++rS;
                }
                ++tmpStart;
            }
            while (lS <= lE) {
                tmp[tmpStart] = a[lS];
                ++tmpStart;
                ++lS;
            }
            while (rS <= rE) {
                tmp[tmpStart] = a[rS];
                ++tmpStart;
                ++rS;
            }
        }
        
        // 可能数组不能刚好分成 x * (len * 2) 段，此时就还会有 “剩余的” 部分
        // “剩余的” 部分又情况是有两种
        // （1）刚好分成两组，但是第二组的元素个数少了，不够 len 个。 此时需要把剩余的这两组也合并了
        // （2）只剩下一组了，该组个数 <= len 个。 此时剩下的一组本身则是有序的，直接放在 a 数组（源数组）的末尾即可，不同处理
        int yushu = a.length % (len * 2);
        if (yushu > 0) {
            if (yushu > len) {
                int lS = tmpStart;
                int lE = lS + len - 1;
                int rS = lE + 1;
                int rE = a.length - 1;
                // 分段的进行归并
                while (lS <= lE && rS <= rE) {
                    if (a[lS] <= a[rS]) {
                        tmp[tmpStart] = a[lS];
                        ++lS;
                    } else {
                        tmp[tmpStart] = a[rS];
                        ++rS;
                    }
                    ++tmpStart;
                }
                while (lS <= lE) {
                    tmp[tmpStart] = a[lS];
                    ++tmpStart;
                    ++lS;
                }
                while (rS <= rE) {
                    tmp[tmpStart] = a[rS];
                    ++tmpStart;
                    ++rS;
                }
                // 如果有剩余的，且是情况（1），则先把剩余部分归并，再存到 a 中
                System.arraycopy(tmp, 0, a, 0, a.length);
            } else {
                // 如果有剩余的，且是情况（2），则剩余的那部分不动即可
                System.arraycopy(tmp, 0, a, 0, a.length - yushu);
            }
        } else {
            // 如果没有余数，则表示刚好可以分成 x * (2 * len) 份
            System.arraycopy(tmp, 0, a, 0, a.length);
        }
        len = len * 2;
    }
}

对于迭代的实现，我这里没有优化代码在书写上的实现，因为迭代的实现有需要注意的地方，即可能数组不能刚好分成 x * (len * 2) 段，此时就还会有 “剩余的” 部分 这里，我想直观的表现出来这种情况是如何处理的。

开始的时候我一直无法正确的处理 “剩余的” 部分 的逻辑，但是后来看了前面提过的图解之后，就能直观的想明白了。

归并排序是一种稳定的排序。