javascript - 意识到 Javascript 表示数组的独特方式的排序

Question

我注意到 Javascript 排序功能在低于 9 的 Internet Explorer 版本中非常慢(与 Firefox 和其他版本相比通常慢一个数量级。我正在实现我自己的版本以查看是否可以做得更好。合并排序工作得很好，但似乎大多数排序算法的文档都假定数组是作为连续的内存块实现的。Javascript 数组是作为对象实现的(至少在旧浏览器中是这样)。

我想知道，是否有一种排序算法考虑到数组访问比平时更昂贵的事实？也就是说，它不仅尝试优化比较次数，还尝试优化访问次数和通过 splice 和 slice 等方式创建新数组的成本。这是我对合并排序的尝试。

function mergeSort(array, compareFunc) {
    if (array.length <= 1) {
        return;
    }
    var mid = Math.floor(array.length/2);
    var left = array.splice(0, mid);
    var right = array.splice(0, array.length);
    mergeSort(left, compareFunc);
    mergeSort(right, compareFunc);

    while ((left.length > 0) && (right.length > 0))
    {
        if (compareFunc(left[0], right[0]) <= 0) {
            array.push(left.shift());
        }
        else {
            array.push(right.shift());
        }
    }
    while (left.length > 0) {
        array.push(left.shift());
    }
    while (right.length > 0) {
        array.push(right.shift());
    }
    return;
}

Answer 1

尝试 Web SQL 排序功能。认为这比 Javascript 中可用的 native 排序更快。如果您正在编写支持跨浏览器兼容性的代码，合并排序是一个很好的算法，但请检查 http://www.cs.princeton.edu/~rs/strings/ .. 这讲述了使用快速排序和基数排序的混合体。

如果能从服务器上获取排序后的数据，那将是最好的方法。