排序算法之归并排序

归并排序

基本思想

归并排序是分治的典型例子(divide-conquer)。总体的步骤为采用分的思想，将问题小化递归求解（分的阶段），然后将小化后的子问题合并得到最终大问题的解。对于排序而言，若细化为两个只有一个数字的数列时对齐合并处理可以很简单地得到有序的数列，归并排序运用的就是这种思想。

算法设计：

整体设计上，算法主要包括分与治这两个过程，

分的设计：

分是递归地解决问题，所以要充分考虑好参数的问题。 参数1：为了节省空间，不会在递归的函数中为分产生的数组分配新的空间，故分的数组是基于原数组空间的，所以需要一个参数为原数组的地址。 参数2与3：另外分主要依靠的是待分数组的左起点和右终点，同时这两个参数也可作为递归终止条件的判断。（这里顺便聊一下递归终止条件的书写，为了使递归有出口，终止条件应当尽量严格，比如在可以写right <= left 和 right == left 的情况下，前者更好，这里相当于偷了个懒，因为不确定分到最后right和left的具体情况） 参数4：考虑到合的过程中需要将结果临时存在一个辅助数组里再赋值到原数组中，故在这里设置一个已经分配好空间的数组指针作为参数。 分析好参数之后，递归就按照宏观思想来写就可以了。即先写终止条件，然后写递归体。

治的设计：

合并数组变得相对简单了。因为合并是在一个数组中的前后两部分进行，所以只需要知道开始点，中点，结束点就可以了。注意，因为采用了递归的设计，最终的结果应当保留到原数组中覆盖之前的结果，别只留在临时数组里。 具体代码如下： （这里为了调用方便包装了一下，所以其实两个函数是够了的）

class solution {
    public void merge(int[] a, int left, int mid, int right, int[] b) {
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if (a[i] < a[j]) {
                b[k++] = a[i++];
            } else {
                b[k++] = a[j++];
            }
        }
        while (i <= mid) {
            b[k++] = a[i++];
        }
        while (j <= right) {
            b[k++] = a[j++];
        }
        k = 0;
        while(left <= right){
            a[left++] = b[k++];
        }
    }

    public int[] merge_sort(int[] input) {
        if(input.length == 1){
            return input;
        }
        int[] result = new int[input.length];
        sort(input, 0, input.length - 1, result);
        return result;
    }

    private void sort(int[] input, int left, int right, int[] result) {
        if (left < right) {
            int mid = (right + left) / 2;
            sort(input, left, mid, result);
            sort(input, mid+1, right, result);
            merge(input, left, mid, right, result);
        }

    }
}