归并排序 java 实现

实现思路

• 将序列每相邻的两个元素进行归并，得到 n/2 个序列，每个序列包含两个元素；
• 再将上述序列归并，每个序列有4个元素
• 重复步骤2
• 最后一步是对两个序列归并，这两个序列的总长度是原数组的长度

和快速排序比较

• 归并排序需要额外的空间，空间复杂度是O（n），快速不需要额外空间
• 归并是稳定的，快排不是稳定的
• 两种排序其实有是有点分治法的味道，将排序拆成一个个小问题，把这些问题组合就得到了原问题的解。
• 快速是先将原数组分成两大块，一块小于中间位置的值，一块大于中间位置的值。再将每块重复上述步骤，直到每块的元素个数为1。是从大往小。
• 归并是讲每个单元素进行合并，再将含有2个元素的序列进行合并，重复上述步骤。是从小往大。

首先实现一个合并算法

代码如下

 * 指定了位置，归并数组 
     *  
     * @param data 
     *            数组 
     * @param low 
     *            起始位置 
     * @param mid 
     *            第一组的截止位置，第二组的起始为 mid+1 
     * @param high 
     *            总截止位置 
     */ 
    private static void merge(Integer[] data, int low, int mid, int high) { 
        if (mid < low || high < mid) { 
            return; 
        } 
 
        // 调试输出 
        System.out.println("2Arrays:" + Arrays.toString(Arrays.copyOfRange(data, low, mid + 1)) 
                + Arrays.toString(Arrays.copyOfRange(data, mid + 1, high + 1))); 
 
        // 构建一个数组，这是归并排序的缺点，需要额外空间 
        Integer[] temp = new Integer[high - low + 1]; 
 
        int l = low; 
        int m = mid + 1; 
        int i = 0; 
 
        while (l <= mid && m <= high) { 
            if (data[l] < data[m]) { 
                temp[i++] = data[l++]; 
            } else { 
                temp[i++] = data[m++]; 
            } 
        } 
 
        // 两个序列最后肯定只剩下一个序列 
        if (l <= mid) { 
            while (l <= mid) 
                temp[i++] = data[l++]; 
        } 
 
        if (m <= high) { 
            while (m <= high) 
                temp[i++] = data[m++]; 
        } 
 
        // 注意这儿 k 从 low 开始，而不是从0 
        int k = low; 
        for (int d : temp) { 
            data[k++] = d; 
        } 
 
        System.out.println("Merged: " + Arrays.toString(Arrays.copyOfRange(data, low, high + 1))); 
 
    } 
 

一趟归并

假设 每个有序表的长度为 range，数字一共有 length/range 个子序列：0~range-1；range ~ range*2-1；等等。
注意有3种情况：
– 有序表的个数为偶数且长度都为 range；
– 有序表的长度为奇数 （最后一个子续表轮空，不考虑）
– 有序表的长度为偶数，最后一个子序列的长度小于 range

 
    /** * 本函数将数组按照以 range 长的小段进行归并 * 数组一共被分为 data.length/range 个小段 * 两两小段归并 会有3种情况： * 1.数组正常被分为偶数个小段 * 2. 数组被分为奇数个小段，最后一个轮空 * 3. 数组被分为偶数个小段，最后一段不完整 * * @param data * 数组，下标从0开始 * @param length */ 
    private static void mergePass(Integer[] data, int range) { 
 
        int i = 0; 
        // 从前往后遍历，把相等的单元归并 
        while (i + 2 * range - 1 < data.length - 1) { 
            merge(data, i, i + range - 1, i + 2 * range - 1); 
            i = i + 2 * range; // 设置 i 新的位置 
        } 
 
        // 这种情况也是有 偶数个小单元，但最后两个小单元一个长一个短 
        if (i + range - 1 < data.length - 1) { 
            merge(data, i, i + range - 1, data.length - 1); 
        } 
 
        // 如果说单元个数为奇数，那么最后一个就没必要归并 
 
        // 最后肯定只剩下两个单元？保证有序？ 
 
    } 

二路归并排序

    /** * 二路归并排序 * @param data 待排序的数组 */ 
    private static void mergeSort(Integer[] data) { 
 
        //len 每次增大一倍 
        int len = 1; 
        while (len < data.length) { 
            mergePass(data, len); 
            len *= 2; 
 
        } 
 
    }

这儿是对上面一趟归并的反复调用，不过每次调用 range 值都增大了一倍。range 最大是 range*2 大于等于 data.length 的时候。

测试程序

    public static void main(String[] args) { 
        Random r = new Random(); 
        Integer[] data = new Integer[r.nextInt(10) + 8]; 
 
        for (int ii = 0; ii < 10; ii++) { 
            for (int i = 0; i < data.length; i++) { 
                data[i] = r.nextInt(30); 
            } 
            System.out.println("------------------------"); 
            System.out.println(Arrays.toString(data)); 
 
            mergeSort(data); 
 
            System.out.println(Arrays.toString(data)); 
        }

输出

------------------------ 
[8, 2, 4, 11, 9, 22, 23, 17, 1, 2, 25, 28, 15, 16, 9, 17] 
2Arrays:[8][2] 
Merged: [2, 8] 
2Arrays:[4][11] 
Merged: [4, 11] 
2Arrays:[9][22] 
Merged: [9, 22] 
2Arrays:[23][17] 
Merged: [17, 23] 
2Arrays:[1][2] 
Merged: [1, 2] 
2Arrays:[25][28] 
Merged: [25, 28] 
2Arrays:[15][16] 
Merged: [15, 16] 
2Arrays:[9][17] 
Merged: [9, 17] 
2Arrays:[2, 8][4, 11] 
Merged: [2, 4, 8, 11] 
2Arrays:[9, 22][17, 23] 
Merged: [9, 17, 22, 23] 
2Arrays:[1, 2][25, 28] 
Merged: [1, 2, 25, 28] 
2Arrays:[15, 16][9, 17] 
Merged: [9, 15, 16, 17] 
2Arrays:[2, 4, 8, 11][9, 17, 22, 23] 
Merged: [2, 4, 8, 9, 11, 17, 22, 23] 
2Arrays:[1, 2, 25, 28][9, 15, 16, 17] 
Merged: [1, 2, 9, 15, 16, 17, 25, 28] 
2Arrays:[2, 4, 8, 9, 11, 17, 22, 23][1, 2, 9, 15, 16, 17, 25, 28] 
Merged: [1, 2, 2, 4, 8, 9, 9, 11, 15, 16, 17, 17, 22, 23, 25, 28] 
[1, 2, 2, 4, 8, 9, 9, 11, 15, 16, 17, 17, 22, 23, 25, 28] ------------------------

从上面的输出可以看出归并的过程。

参考文章

http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.5.1.1.htm