Javascript合并算法的实现(递归&迭代)

1,522 阅读1分钟

使用分治法将需要排序的内容一分为二,二分为四,四分为八……

将内容分解到通过最后单独比较大小的粒度,进行排序,然后将内容八并为四,四并为二,二并为一。


1、递归实现:

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());
        }
    }
    return result.concat(left).concat(right);
}

function mergeSort(items){
    if(items.length==1){
        return items;
    }
    var half = Math.floor(items.length/2),
        left = items.slice(0,half),
        right = items.slice(half);
    return merge(mergeSort(left),mergeSort(right));
}

逻辑比较简单,一个是merge函数,用来排序内容。mergeSort函数用来将内容划分到最小粒度。缺点是当内容长度到达一定限度后,会发生栈溢出错误。


2、迭代实现:

function mergeSort(items){
    var len = items.length;
    if(len==1){
        return items;
    }
    var result = [];
    for(var i=0;i<len;i++){
        result.push([items[i]]);
    }
    if(len%2){
        result.push([]);
    }
    var lim = len/2;
    while(lim>=1){
        for(var j=0,k=0;j<lim;j++,k=k+2){
            result[j] = merge(result[k],result[k+1]);
        }
        lim = lim/2;
    }
    return result[0];
}

实现逻辑和递归调用不同,迭代的实现方式,是通过操作某一个数组,合并该数组实现的。不会存在栈溢出问题,但是效率会低于递归。