基本思想

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。
这里写图片描述
可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。

实现步骤

我们来看看治阶段。我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。
这里写图片描述

参考代码

merge_sort()

void merge_sort(int[] array, int p ,int r) {
    if(p < r) {
        int q = (p + r) / 2;
        merge_sort(array , p ,q);
        merge_sort(array , q+1 ,r);
        merge(array , p ,q , r);
    }
}

merge()

void merge(int[] array , int p , int q ,int r) {
        int n1 = q-p+2;
        int n2 = r-q+1;
        int[] L = new int[n1];
        int[] R = new int[n2];
        for(int i = 0;i < n1-1; i++)
            L[i] = array[p + i];
        for(int j = 0 ; j < n2-1; j++)
            R[j] = array[q + j + 1];
        L[n1-1] = Integer.MAX_VALUE;
        R[n2-1] = Integer.MAX_VALUE;
        for(int k = p , i = 0 , j = 0; k <= r ;k++) {
            if(L[i] <= R[j]) {
                array[k] = L[i];
                i++;
            }
            else {
                array[k] = R[j];
                j++;
            }
        }
    }

主函数与测试用例

这里的测试用例需要手动输入若干个数字。并使用空格键隔开：

public static void main(String[] args) {
        int[] array = new int[8];
        Scanner in = new Scanner(System.in);
        for(int i = 0; i< array.length; i++)
            array[i] = in.nextInt();
        Homework_ds3 mergeSort = new Homework_ds3();
        mergeSort.merge_sort(array, 0, 7);
        for(int i : array)
            System.out.println(i);
    }