引言

    对于编程中琳琅满目的算法，本人向来是不善此道也不精于此的，而说起排序算法，也只是会冒泡排序。还记得当初刚做开发工作面试第一家公司时，面试官便让手写冒泡排序（入职之后才知道，这面试官就是一个冒泡排序"病态"爱好者，逢面试必考冒泡排序-__-）。后来看吴军的一些文章，提到提高效率的关键就是少做事情不做无用功，便对这不起眼的排序算法有了兴趣。刚好今天周末有闲，遂研究一二，与各位道友共享。

    冒泡排序时间之所以效率低，就是因为将所有数都一视同仁不做区分挨个比较，这是最普通的做事方法，所以效率也是最普通的，时间复杂度为N的平方；而归并排序效率高，则是采用了分治的思想，将一个整体分成多个小份，每个小份排好序之后再互相比较，这样就比冒泡快了不少，时间复杂度为NlogN；快速排序的平均时间复杂度也是NlogN，但是实际的耗费时间会比归并排序快两三倍（当然快排在最坏的情况下时间复杂度还是N的平方，比归并排序大），它的平均执行时间能比归并更快一些是因为它每次分组时不是随机分组而是相对有序的分组，即先从数组中随机取一个数作为基数，然后将数据移动，使得基数一边的数都比它小，另一边的数都比它大，再在两边各取一个基数进行相同的移动、分组操作，递归下去，这样每个细分的小组都在整体的大数组中有个位置，合并时直接按从小到大将各个分组合并起来即可，所以一般情况下会比归并快一些。

    了解了思想之后，再用代码实现相对就会容易很多。此处就再借用一个直观一点的例子来说明归并与快排二者的区别。假设有1000个学生，想对他们的成绩进行排序。方法1借用归并排序的思想，具体这样做：将这1000个人分成10组，将每组的100人进行排序，排完之后再在各组之间从小到大依次进行比较，最后得到整个的成绩排名。方法2借用快速排序的思想，具体需这样做：将1000个人也是分成10组，但是是按分数段分，0-10分的放在一组，10-20分的放在一组，20-30分的放在一组，依次类推，分完组之后再在各个小组中进行排序，而当你合并各个小组时，只需将其按从小到大的顺序直接合并就行，无需跟方法1一样将各小组中的数据取出来跟其他小组中的数据挨个比较。看到这里，想必各位道友对快排比归并排序还要快一些的原因就有了解了。

    算法可以理解成做事的技巧或者说套路，我们对其的理解可以不止于编程，完全可以推广出去。比如归并的分治法，将一个大事情拆解成多个小事件，解决起来就会方便很多。闲话扯了一大堆，下面就将我自己写的排序给大家贴出来，附带上注释讲解，如果有之前不了解的道友，相信看完之后便会念头通透，原地飞升 >_<。

正文

归并排序

// 归并排序
    public static void mergeSort (int[] arr) {
        // 建一个临时数据来存放数据
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
    }

    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) { // 如果起始下标跟结束下标差值小于1，则不进行操作
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid, temp); // 分组，将左边分为一组，递归调用进行排序
            mergeSort(arr, mid+1, right, temp); // 将右边分为一组
            merge(arr, left, mid, right, temp); //将左右分组合并
        }
    }