算法（三）--归并排序

归并算法思想

1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2.设定两个指针，最初位置分别为两个已经排序序列的起始位置
3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4.重复步骤3直到某一指针超出序列尾将另一序列剩下的所有元素直接复制到合并序列尾
图示如下：

image

根据图示代码如下：

 /**
 * 归并排序   递归方式
 * @param {* 需要排序的数组} arr 
 * @param {* 数组长度} n 
 */
this.mergeSort = (arr, n) => {
    var _this = this
    //传入n-1是保证 数组 arr 是[l,mid][mid+1,r]是两个保单左右端的闭区间
    __mergeSort(arr, 0, n - 1)
    //归并两个闭区间
    function __merge(arr, l, mid, r) {
        let result = arr;
        let i = l, j = mid + 1;
        for (let k = l; k <= r; k++) {
            if (i > mid) {
                arr[k] = result[j - l]
                j++
            } else if (j > r) {
                arr[k] = result[i - l]
                i++
            } else if (arr[i - l] < arr[j - l]) {
                arr[k] = result[i - l]
                i++
            } else {
                arr[k] = result[j - l]
                j++
            }
        }
    }
    //递归分解
    function __mergeSort(arr, l, r) {
        if (l >= r) {
            return
        }
        //尝试优化  存在bug
        // if (r - l <= 2) {
        //     _this.insertionSort2(arr, l, r)
        //     return
        // }

        //l+r可能超出计算机的最大数值
        let mid = Math.floor((l + r) / 2)
        __mergeSort(arr, l, mid)
        __mergeSort(arr, mid + 1, r)
        //对于近乎有序数组的排序优化
        //因为每一次__merge都会保证 l到mid是有序的  mid到 r是有序的
        if (arr[mid] > arr[mid + 1]) {
            __merge(arr, l, mid, r)
        }
    }
}

代码解析

__mergeSort函数递归分解需要排序的数组，当L>=r时停止递归。
__merge归并两个闭区间，将两个有序的数组合并成一个。

下面介绍另外一种归并排序，使用迭代的方式，或者说自底向上的方式。

/**
 * 归并排序   自底向上
 * 相比较于是比递归方式要慢一点   可以很好的对链表数据结构排序nlogon级别的排序
 * @param {* 需要排序的数组} arr 
 * @param {* 数组长度} n 
 */
this.mergeSortBu = (arr, n) => {
    for (let size = 1; size < n; size += size) {
        for (let i = 0; i + size < n; i += size + size) {
            let max = i + size + size - 1 > n - 1 ? n - 1 : i + size + size - 1
            //排序优化
            if (arr[i + size - 1] > arr[i + size]) {
                //对 [i,i+size-1]和[i+size,i+size+size-1]进行归并
                __merge(arr, i, i + size - 1, max)
            }
        }

    }

    function __merge(arr, l, mid, r) {
        let result = arr;
        let i = l, j = mid + 1;
        for (let k = l; k <= r; k++) {
            if (i > mid) {
                arr[k] = result[j - l]
                j++
            } else if (j > r) {
                arr[k] = result[i - l]
                i++
            } else if (arr[i - l] < arr[j - l]) {
                arr[k] = result[i - l]
                i++
            } else {
                arr[k] = result[j - l]
                j++
            }
        }
    }
}

图示如下：

归并排序.png

将数组分成数组长度分，从下往上进行合并。每一次size*2.这样做我觉得的可能好理解一点。

以上都是个人理解如有不对之处还望指正交流！