一图看懂归并排序

归并排序采用的是分治的思想，首先是“分”，将一个数组反复二分为两个小数组，直到每个数组只有一个元素；其次是“治”，从最小数组开始，两两按大小顺序合并，直到并为原始数组大小

归并排序

归并排序（MERGE-SORT）是利用分治的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

分

"分"就是将原始数组逐次二分，直到每个数组只剩一个元素，一个元素的数组自然是有序的，所以就可以开始“治”的过程了。

治

"治"实际上是将已经有序的数组合并为更大的有序数组。那怎么做呢?就是创建一个新数组，比较left[0]和right[0] ，那个比较小就将那个的值放进新数组，然后再继续比较left[0]
和right[1]，或者是left[1]和right[0]。可以看出数组left，right都只需遍历一遍，所以对两个有序数组的排序的时间复杂度为O(n)。

算法描述

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

动图展示

归并排序.gif

时间复杂度分析：分的过程需要三步：log8 = 3，而每一步都需要遍历一次8个元素，所以8个元素共需要运行 8log8 次指令，那么对于 n 个元素，时间复杂度为 O(nlogn)。

代码实现

js版本：

function mergeSort(arr) {
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}
 
function merge(left, right) {
    var result = [];
 
    while(left.length>0 && right.length>0) {
        if(left[0] <= right[0]) {
            result.push(left.shift());
        }else{
            result.push(right.shift());
        }
    }
 
    while(left.length)
        result.push(left.shift());
 
    while(right.length)
        result.push(right.shift());
 
    return result;
}

java版本：

// 归并排序（Java-递归版）
    static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {
        if (start >= end)
            return;
        int len = end - start, mid = (len >> 1) + start;
        int start1 = start, end1 = mid;
        int start2 = mid + 1, end2 = end;
        merge_sort_recursive(arr, result, start1, end1);
        merge_sort_recursive(arr, result, start2, end2);
        int k = start;
        while (start1 <= end1 && start2 <= end2) {
            result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
        }
        while (start1 <= end1) {
            result[k++] = arr[start1++];
        }
        while (start2 <= end2) {
            result[k++] = arr[start2++];
        }
        for (k = start; k <= end; k++) {
            arr[k] = result[k];
        }
    }

    public static int[] merge_sort2(int[] arr) {
        int len = arr.length;
        int[] result = new int[len];
        merge_sort_recursive(arr, result, 0, len - 1);
        return result;
    }

朵拉姐【ITI2018】的前端摸鱼技术群

欢迎大家技术交流 内推 摸鱼 求助皆可 - 链接

系列链接（后续都会更新完毕）

• 终于理解希尔排序与插入排序

• 一图看懂快速排序

• 插入排序（Insertion Sort）

• 冒泡排序与选择排序的区别