javascript - 为什么说这是‘原地排序’？

最近看Nicholas大神的JS算法博客（原文地址：Computer science in JavaScript: Merge sort），在这里他实现两种归并排序，第一种是非原地排序，第二种是原地排序。我觉得这两种方式的空间复杂度都一样，区别只在于其返回值是否原数组，Nicholas说第二种是原地排序，但我之前看的原地排序的概念不是说跟额外的空间复杂度有关吗？而在这篇博客里的原地排序与空间复杂度好像没有关系。那原地排序的概念到底是指什么呢，按照Nicholas的说法是否可以理解为只要是在原数组上处理就是原地排序呢？

这里贴出原文中的代码：

注意：该博客中的例子只为阐述概念，并不强调性能

非原地排序实现归并：

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(items){

if (items.length < 2) {
    return items;
}

var middle = Math.floor(items.length / 2),
    left    = items.slice(0, middle),
    right   = items.slice(middle),
    params = merge(mergeSort(left), mergeSort(right));

// Add the arguments to replace everything between 0 and last item in the array
params.unshift(0, items.length);
items.splice.apply(items, params);
return items; 
}

公共函数merge：

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));
}

天蓬老师2776 天前353

javascript - 为什么说这是‘原地排序’？

全部回覆(1)我來回復