归并排序

java 3 2016-02-29 13:03
女装

概述

归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序采用的是递归来实现,属于“分而治之”,将目标数组从中间一分为二,之后分别对这两个数组进行排序,排序完毕之后再将排好序的两个数组“归并”到一起,归并排序最重要的也就是这个“归并”的过程,归并的过程中需要额外的跟需要归并的两个数组长度一致的空间。

效果图:

步骤

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置

  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

  4. 重复步骤3直到某一指针达到序列尾

  5. 将另一序列剩下的所有元素直接复制到合并序列尾

实例

原始数据:

3 5 2 6 2

归并的前提是将数组分开,一分为二,再一分为二,分到不能再分,进行归并。

第一轮分隔,索引2 ((0+4)/2=2) 为中间

[3 5 2] [6 2]

第二轮分隔,对[3 5 2]进行分隔

[3 5] [2] [6 2]

第三轮分隔,对[3 5]进行分隔

[3] [5] [2] [6 2]

合并[3] [5]

[3 5] [2] [6 2]

合并[3 5] [2]

[2 3 5] [6 2]

第四轮分隔,对[6 2]进行分隔

[2 3 5] [6] [2]

合并[6] [2]

[2 3 5] [2 6]

合并[2 3 5] [2 6]

[2 2 3 5 6]

代码实现(Java)

package com.coder4j.main.arithmetic.sorting;

public class Merge {
    
    private static int mark = 0;

    /**
     * 归并排序
     * 
     * @param array
     * @param low
     * @param high
     * @return
     */
    private static int[] sort(int[] array, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            mark++;
            System.out.println("正在进行第" + mark + "次分隔,得到");
            System.out.println("[" + low + "-" + mid + "] [" + (mid + 1) + "-" + high + "]");
            // 左边数组
            sort(array, low, mid);
            // 右边数组
            sort(array, mid + 1, high);
            // 左右归并
            merge(array, low, mid, high);
        }
        return array;
    }

    /**
     * 对数组进行归并
     * 
     * @param array
     * @param low
     * @param mid
     * @param high
     */
    private static void merge(int[] array, int low, int mid, int high) {
        System.out.println("合并:[" + low + "-" + mid + "] 和 [" + (mid + 1) + "-" + high + "]");
        int[] temp = new int[high - low + 1];
        int i = low;// 左指针
        int j = mid + 1;// 右指针
        int k = 0;
        // 把较小的数先移到新数组中
        while (i <= mid && j <= high) {
            if (array[i] < array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }
        // 两个数组之一可能存在剩余的元素
        // 把左边剩余的数移入数组
        while (i <= mid) {
            temp[k++] = array[i++];
        }
        // 把右边边剩余的数移入数组
        while (j <= high) {
            temp[k++] = array[j++];
        }
        // 把新数组中的数覆盖array数组
        for (int m = 0; m < temp.length; m++) {
            array[m + low] = temp[m];
        }
    }

    /**
     * 归并排序
     * 
     * @param array
     * @return
     */
    public static int[] sort(int[] array) {
        return sort(array, 0, array.length - 1);
    }

    public static void main(String[] args) {
        int[] array = { 3, 5, 2, 6, 2 };
        int[] sorted = sort(array);
        System.out.println("最终结果");
        for (int i : sorted) {
            System.out.print(i + " ");
        }
    }
}

测试输出结果:

正在进行第1次分隔,得到
[0-2] [3-4]
正在进行第2次分隔,得到
[0-1] [2-2]
正在进行第3次分隔,得到
[0-0] [1-1]
合并:[0-0][1-1]
合并:[0-1][2-2]
正在进行第4次分隔,得到
[3-3] [4-4]
合并:[3-3][4-4]
合并:[0-2][3-4]
最终结果
2 2 3 5 6 

经测试,与实例中结果一致。

女装
文章评论