归并排序算法

1、概念

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。想要详细了解算法的可以参考图解排序法这篇文章，本文是记录一下自己用js写算法的思路，一步步从简单到完善。本文的归并排序我们采用递归去实现。

如上图所示，我们需要不断地拆分我们的数据，使得每一部分只有一项，然后再分组归并，进行分而治之。可以看到这种结构很像一棵完全二叉树。下面分享一下，我的实现思路。

2、实现思路

我们由简入繁，先排序只有两项的数组。先实现拆分数据mergeSort方法，然后进调用merge方法，进行归并排序。

2.1 拆分

        //拆分
        function mergeSort(arr) {
            //数据一分为二
            let mid = Math.floor(arr.length / 2);
            let leftArr = arr.slice(0, mid);
            let rightArr = arr.slice(mid);
            return merge(leftArr, rightArr);
        }

很简单直白的把数组一分为二，进行排序

2.2 归并

    //归并
        function merge(leftArr, rightArr) {
            let result = [];//临时数组，保存排序后的数组
            if (leftArr[0] < rightArr[0]) {
                result.push(leftArr.shift());
            } else {
                result.push(rightArr.shift());
            }
            return result.concat(leftArr).concat(rightArr);
        }

归并排序时，我们创建一个临时数组保存排序后的数据；每个数组只有一项，所以我们都取出第一项进行比较（push，shift，concat不太清楚的自己百度一下吧），最后不管if else走哪一步，leftArr和rightArr中较大者没有加入临时数组result 中，所以把三个数组都连接，最后的result就一定包含leftArr和rightArr的所有项且是有序的。

2.3 验证

        let arr = [6, 4];  
        console.log(mergeSort(arr));//[4, 6]

结果没问题，现在我们把数组改成三项，

      let arr = [6, 4, 1];
      console.log(mergeSort(arr));//[4, 6, 1]

发现第三项的1并没有排序正确，下面我们来改造方法，实现大于两项的数组的排序。
归并排序的要求是什么？要不断拆分，最后每一部分只有一项，上面的拆分显然没有做到；另外，在归并排序时，我们只做了数组第一项的比较，后面的并没有比较，所以第三项没有排序。下面我们就将代码的缺点进行改造。

2.4 拆分改造

我们把数组一分为二，两个数组都有可能有多项，所以我们还得对leftArr和rightArr数组进行拆分,所以我们可以采用递归的方式拆分，这里注意了，只有一项是不用拆分了，我们这里加个控制，直接返回只有一项的数组即可。

        //拆分
        function mergeSort(arr) {
         //如果数组小于等于一项，不用在再拆
          if (arr.length <= 1) return arr;
            //数据一分为二
            let mid = Math.floor(arr.length / 2);
            let leftArr = arr.slice(0, mid);
            let rightArr = arr.slice(mid);
            return merge(mergeSort(leftArr), mergeSort(rightArr));
        }

这样我们就能保障拆分的每一部分最后只有一项的数组了。

2.5 归并改造

都知道比较需要加循环，那我们思考一下，怎么做才最简单？我们上面采用了数组的shift()方法，每次取出第一项（这个方法会改变原数组的）放入临时数组中。所以数组进行shift()方法后，第一项其实是原来数组的第二项了；另外，每一个数组都是排序排好（递归的结果），所以循环比较后，leftArr和rightArr数组必定有一个是空数组了，那循环的条件显而易见了：判断leftArr和rightArr数组长度。

        //归并
        function merge(leftArr, rightArr) {
            let result = [];//临时数组，保存排序后的数组
            while (leftArr.length > 0 && rightArr.length > 0) {
                if (leftArr[0] < rightArr[0]) {
                    result.push(leftArr.shift());
                } else {
                    result.push(rightArr.shift());
                }
            }
            return result.concat(leftArr).concat(rightArr);
        }

2.6 再次验证

        let arr = [6, 4, 1];
        console.log(mergeSort(arr));//[1, 4, 6]
        let arr2 = [6, 4, 1,3,12,14,32,9,8];
        console.log(mergeSort(arr2));//[1, 3, 4, 6, 8, 9, 12, 14, 32]

算法很简单，关键是实现的思路，我们不必要一上来就排序项目很多的数组。可以由特例入手，发现不足之处，找到和我们的算法思路不相符合的地方去补足去完善。

总结

归并排序是稳定排序，是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。