排序知道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 中可用的本机排序更快。如果您正在编写支持跨浏览器兼容性的代码，合并排序是一个很好的算法，但请检查http://www.cs.princeton.edu/~rs/strings/ ..这讲述了如何使用快速排序的混合和基数排序。

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