java实现排序(5)-归并排序

引言

归并排序也是一种效率非常高的排序算法，它的时间复杂度是O（NlogN）。在本文中，会详细介绍归并排序的概念和排序的基本原理。最后用代码实现归并排序，供大家参考。笔者目前整理的一些blog针对面试都是超高频出现的。大家可以点击链接：http://blog.csdn.net/u012403290

技术点

1、分治策略
在如今处理大数据和有效提高执行效率的方法，分治策略显得非常的普及。比如在前几篇博文《java中不常见的东西-Fork/join》其实就是一种分治策略。通俗来说，就是把一个问题分而治之。“分”：它把一个大问题分成一些小的问题，然后通过递归求解。“治”：把各个分后的小问题的答案统筹合并在一起。或许你听过map-reduce。都是体现了这种思想，对计算机资源也是一种充分利用的体现。

2、归并排序
通俗来说，核心就是合并两个已排好序的数据，那么对于这个步骤来说显得非常好理解，我们只需要设立2个指针，分别指向预处理的两个有序数据的比较位置，同时设立一个新的存储容器，把比较之后合适的值放入这个新的容器中，再把对应的指针往后移动一位。接下来，我们图解一下如何实行归并排序的：

存在三个数组A、B和C，A和B本身就是有序的，C是一个长度合适的空数组，用于存储新的数据。我们再设立三个指针，分别指向A、B和C当前操作的位置。初始阶段如下图：
这里写图片描述
在初始阶段中，C数组的容量是A与B的容量之和。每个数组的指针都指向数组第一个位置。

①归并排序第一步，比较A[0]与B[0]，也就是A指针与B指针指向的地方，发现3<5，所以把3放入C数组中的C[0]位置，也就是C指针指向的地方。在后述中，我们只用指针指向来标志处理的位置。只要对数据进行了处理，那么指针就需要往后移动一位，第一步的比较之后，就变成了这样：
这里写图片描述
在数组A和C中指针发生了变化，因为A产出了一个3，C接收了一个3，而B数组数据没有发生变化。

②我们继续比较A与B数组指针指向的位置，发现15>5，那么我们就把5放入C数组指针指向的地方。因为B产出了5，C接收了5，而A数组没有变化，所以B与C的指针向后移动一位，就变成了这样：
这里写图片描述

③继续比较A与B数组指针指向的位置，发现15<18，那么就把15放入C数组指针指向位置，因为A与C数组变得，把两者的指针向后移动一位：
这里写图片描述

④继续比较A与B数组指针指向位置，发现21>18，那么把18放入C数组指针指向位置，B与C数组指针向后移动一位：
这里写图片描述

⑤继续比较A与B数组指针指向位置，发现21>20，那么把20放入C数组，并移动相关指针：
这里写图片描述

⑥不再赘述，直接放图：
这里写图片描述

⑦不再赘述，直接放图：
这里写图片描述
在上图中，我们发现A数组已经使用完了，当这种情况出现，比较也就结束了，直接把B数组剩余的部分放到C数组从指针开始的尾部。排序就结束了

⑧A数组已使用完毕，直接把B数组剩余数据拷贝到C数组以指针指向位置为起点的位置上：
这里写图片描述

我们总结一下上面的步骤，在归并排序中合并两个有序的数据的时间是线性的，最多比较两组数据总和-1次。那么，在整体对一系列数据进行归并排序，第一步就需要把它拆分为一个数据为一个有序数组为止（因为单个数据总是有序的）,比较相邻有序数据，合并成一个新的数组。然后又把临近的两个新的有序数组再次归并比较，又得到一个新的数组，以此类推。比如说下面这个例子：

原数据：5，9，1，6，2，7，8
初始化：{5}，{9}，{1}，{6}，{2}，{7}，{8}
第一趟归并：{5，9}，{1，6}，{2，7}，{8}
第二趟归并：{1，5，6，9}，{2，7，8}
第三趟归并：{1，2，5，6，7，8，9}

代码实现

思考：
1、在分治策略中，递归是必然存在的，所以在设计代码的时候，如何掌握递归显得非常重要。递归的部分肯定是把数据拆分成小组，再把小组拆分成更小的组，直至拆分为1个数据（1个数据就是有序的）。那么递归的临界条件就是数据长度大于1。

2、我们必然存在一个c数组去存储排好序的数据。但是我们可以思考，如果在排序部分创建一个中间数组来存储，那么不断循环的new出一个新数据，对系统开销会显得非常大。我们考虑上面说到的两个有序数组进行整合成c数组，我们发现：
我们可以把一个预排序数组在逻辑上拆分为两个有序数组进行有序合并（实际上是一个数组），同时合并完之后，把合并部分回归到原始数组。如此这般，我们还不用一直创建新的c数组，只需要创建一个，只是指针指向不同罢了。下面图解上面这段逻辑：
这里写图片描述

以下是代码实现：

package com.brickworkers;

public class MergeSort<T extends Comparable<? super T>> {

    //核心两组有序数据合并算法,注意在这里并没有明显拆分出2个数组，只是在同一个数组中引用
    private void merge(T[] target, T[] store, int a_pointer, int b_pointer, int end){//入参为一个要排序的数组和两个数组的指针，和当前处理数组的长度
        //a数组的结尾
        int ae_pointer = b_pointer - 1;//b数组第一个节点左移一位就是a数组的结尾
        int store_pointer = a_pointer; //这个就是c数组的指针，也就是存储数组的指针，这样做的目的是能动态的变动这个数组
        int element_size = end - a_pointer + 1;//这个表示当前处理元素数量

        //while循环，如果数组没有用完就一直循环
        while(a_pointer <= ae_pointer && b_pointer <= end){
            if(target[a_pointer].compareTo(target[b_pointer]) <= 0){//如果a数组指针指向位置小于b指针指向位置，那么就要把a数据存储到c中，并移动指针
                store[store_pointer++] = target[a_pointer++];
            }else{
                store[store_pointer++] = target[b_pointer++];
            }
        }


        //如果某一个数组用完，那么需要把另外一个数组拷贝到c数组中
        while(a_pointer <= ae_pointer){//b数组用完，则把a数组剩余拷贝到c中
            store[store_pointer++] = target[a_pointer++];
        }

        while(b_pointer <= end){//a数组用完，则把b数组剩余拷贝到c中
            store[store_pointer++] = target[b_pointer++];
        }


        //我们把排序好的部分放入目标数组中
        for (int i = 0; i < element_size; i++, end--) {
            target[end] = store[end];
        }
    }



    private void mergeSort(T[] target, T[] store, int start, int end){//需要排序的目标数组
        //递归临界条件，数组必须存在
        if(end > start){
            //把目标数据拆分为两部分
            int mid = (start + end)/2;
            //左边的数组排序
            mergeSort(target, store, start, mid);
            //右边的数组排序
            mergeSort(target, store, mid + 1, end);

            //执行归并
            merge(target, store, start, mid+1, end);
        }
    }


    public void mergeSort(T[] target){//方法我们主要是把c数组，也就是存储数组单独拿出来创建，这样一来只会创建一次,可以有效提升效率
        T[] store = (T[]) new Comparable[target.length];
        mergeSort(target, store, 0, target.length - 1);
    }


    public static void main(String[] args) {
        MergeSort<Integer> sort = new MergeSort<Integer>();
        Integer[] target = {6,5,9,7,5,8,4,2,1};
        sort.mergeSort(target);
        for (Integer integer : target) {
            System.out.print(integer + " ");
        }

    }
}


//输出结果：
//1 2 4 5 5 6 7 8 9 
//