Javascript和归并排序

Javascript和归并排序

这里以递归为例，参考自慕课网刘波波老师的C++版本实现

普通归并(自上而下)

普通的归并排序，是把数据自上而下地分成若干个小块，然后在小块里进行合并排序的操作，最后不断重复这个过程，得到最终的结果。
代码就是这样的：

var mergeSort = function (arr) {
    __mergeSort(arr, 0, arr.length - 1);
    return arr;
}

function __mergeSort(arr, start, end) {
    //健壮性
    if (start >= end) {
        return;
    }
    var mid = ~~((start + end) / 2);
    //递归
    __mergeSort(arr, start, mid);
    __mergeSort(arr, mid + 1, end);
    //处理
    __merge(arr, start, mid, end);

}

function __merge(arr, start, mid, end) {
    //数组副本
    var aux = arr.slice(start, end + 1);
    var i = start;
    var j = mid + 1;
    for (var k = start; k <= end; k++) {
        //这里可以合并代码
        // 左边的归并完了，右边的没有归并完
        if (i > mid) {
            arr[k] = aux[j - start];
            j++;
        }
        //右边的归并完了，左边的没有归并完
        else if (j > end) {
            arr[k] = aux[i - start];
            i++;
        }
        // 左边小
        else if (aux[i - start] < aux[j - start]) {
            arr[k] = aux[i - start];
            i++;
        }
        // 右边小
        else {
            arr[k] = aux[j - start];
            j++;
        }
    }
    return arr;
}

优化归并(自下而上)

我们经过观察就会发现，其实可以省略分块的步骤，直接最开始的时候把它们看做一个个小的数据块，从而自下而上的一步步合并得到最终的结果。
代码就变成了这样：

var mergeSortBU = function (arr) {
    var len = arr.length;
    for (var sz = 1; sz <= len; sz += sz) {
        for (var i = 0; i + sz < len; i += sz + sz) {
            __merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, len - 1));
        }
    }
    return arr;
}
function __merge(arr, start, mid, end) {
    //数组副本
    var aux = arr.slice(start, end + 1);
    var i = start;
    var j = mid + 1;
    for (var k = start; k <= end; k++) {
        // 左边的归并完了，右边的没有归并完或者左边大
        if (i > mid || (aux[i - start] >= aux[j - start])) {
            arr[k] = aux[j - start];
            j++;
        }
        else {
            arr[k] = aux[i - start];
            i++;
        }
    }
    return arr;
}

同时排序一百万个数据时的性能对比：

归并排序耗时.png

可以看出，第二个方案总体上来说是比第一个方案好的。

JS特色归并

这种写法当然是使用了大量JS原生API的，在这里我给出我的写法和阮一峰先生的写法：

//我的写法
function mergeSort(arr) {
    var len = arr.length;
    for (var sz = 1; sz <= len; sz += sz) {
        for (var i = 0; i + sz < len; i += sz + sz) {
            var left = arr.slice(i, i + sz);
            var right = arr.slice(i + sz, Math.min(i + sz + sz, len));
            arr.splice(i, Math.min(sz + sz,len ), ...merge(left, right));
        }
    }
    return arr;
}

// 有性能损失
function merge(left, right) {
    var tmp = [];
    while (left.length && right.length) {
        //左小出右
        if (left[0] < right[0]) {
            tmp.push(left.shift());
        }
        //右小出右
        else {
            tmp.push(right.shift());
        }
    }
    return tmp.concat(left, right);
}

//阮一峰老师的实现
function merge(left, right){
    var result  = [],
        il      = 0,
        ir      = 0;
    while (il < left.length && ir < right.length){
        if (left[il] < right[ir]){
            result.push(left[il++]);
        } else {
            result.push(right[ir++]);
        }
    }
    return result.concat(left.slice(il)).concat(right.slice(ir));
}

function mergeSort(myArray){
    if (myArray.length < 2) {
        return myArray;
    }

    var middle = Math.floor(myArray.length / 2),
        left    = myArray.slice(0, middle),
        right   = myArray.slice(middle),
        params = merge(mergeSort(left), mergeSort(right));
    
    // 在返回的数组头部，添加两个元素，第一个是0，第二个是返回的数组长度
    params.unshift(0, myArray.length);

    // splice用来替换数组元素，它接受多个参数，
    // 第一个是开始替换的位置，第二个是需要替换的个数，后面就是所有新加入的元素。
    // 因为splice不接受数组作为参数，所以采用apply的写法。
    // 这一句的意思就是原来的myArray数组替换成排序后的myArray
    myArray.splice.apply(myArray, params);

    // 返回排序后的数组
    return myArray;
}

这两个算法，性能上都差之前实现的很多，并且数据量到一百万的时候还是导致溢出，有兴趣的朋友可以自己去试试。

总结

归并算法和排序算法一样是利用了分治法来解决问题：即先解决若干个小问题就等于解决了一个大问题。