JavaScript,使用第二个参数排序更快

Question

我做了一些测试,发现它array.sort(function(a, b) { return a - b; });比array.sort();JavaScript 快得多.

结果令人震惊,IE9快1.7倍,FF7 1.6倍,Chrome浏览器6.7倍.

另外,通过我自己在JS中实现快速排序,我发现它比上面提到的两种方法都要快.(两种不同的实现,一种接受比较器函数作为参数,另一种不接受.两者都更快.)

有没有合理的解释？

编辑:我的实现:

没有比较者:

function quickSort(array, from, to) {
    if(typeof from === 'undefined') {
        from = 0;
        to = array.length - 1;
    }
    else if(typeof to === 'undefined') {
        to = array.length - 1;
    }

    if(to - from < 1) {
        return;
    }

    var i = from, pivot = to, t;

    while(i < pivot) {
        if(array[i] > array[pivot]) {
            t = array[i];
            array[i] = array[pivot - 1];
            array[pivot - 1] = array[pivot];
            array[pivot] = t;
            pivot--;
        }
        else {
            i++;
        }
    }

    quickSort(array, from, pivot - 1);
    quickSort(array, pivot + 1, to);
}

用比较器:

function quickSortFunc(array, sortfunc, from, to) {
    if(typeof from === 'undefined') {
        from = 0;
        to = array.length - 1;
    }
    else if(typeof to === 'undefined') {
        to = array.length - 1;
    }

    if(to - from < 1) {
        return;
    }

    var i = from, pivot = to, t;

    while(i < pivot) {
        if(sortfunc(array[i], array[pivot]) > 0) {
            t = array[i];
            array[i] = array[pivot - 1];
            array[pivot - 1] = array[pivot];
            array[pivot] = t;
            pivot--;
        }
        else {
            i++;
        }
    }

    quickSortFunc(array, sortfunc, from, pivot - 1);
    quickSortFunc(array, sortfunc, pivot + 1, to);
}

Answer 1

有两个因素在起作用：

首先，正如 Felix King 在评论中提到的，本机排序方法在比较之前将每个数组成员转换为字符串。如果所有（或大多数）数组成员都是数字，则使用function(a, b) { return a - b; }速度会更快。

其次，排序算法是依赖于实现的。您可能知道也可能不知道，如果将新元素插入到已经排序的数组中，快速排序的性能会非常糟糕。也许这就是 WebKit 决定实现选择排序的原因。

但不要害怕，帮助就在附近！有人已经分叉了 WebKit 来解决这个问题