JavaScript: 数组排序优化

Question

我有一个JavaScript数组，其中包含嵌套的对象，示例如下：[{id:1, position: 1}, {id:2, position: 2}, {id:3, position: 3}, {id:4, position: 4}, {id:7, position: 7}, {id:5,position:5},{id:6, position: 6}]。这只是一个例子，实际上我在我的应用程序中有一个包含100条记录的数组。我试图使用JavaScript数组sort方法对该数组进行排序。假设数组名称为myArray，我正在执行以下操作：

myArray.sort(function(a, b) {
   return a.position- b.position;
});

它可以正常工作，但会冻结我的浏览器。是否有更好的优化方法来进行排序。

- Deepak Biswal

---

这些数据来自某种请求吗？如果是的话，在传输数据之前最好让服务器对数据进行排序。 - Frédéric Hamidi

导致浏览器冻结的因素可能是：极长的数组、极深的嵌套或极其复杂的排序回调函数。从您所写的内容来看，似乎都不是这种情况。也许您需要提供更多关于数据和排序回调函数的详细信息。 - lxg

请查看JavaScript原型风格的快速排序实现：http://codereview.stackexchange.com/questions/47963/quick-sort-implementation-in-javascript-in-prototype-style。不确定它是否适用于100条记录。 - malkassem

为了在正确的位置添加一个项目，最好通过线性搜索找到该位置，然后在那里添加它，这样更有效率。 - fast

为了预测新位置，我还需要循环遍历现有数组，并查找新对象根据其位置属性设置的位置！ - Deepak Biswal

Answer 1

在您最近的一条评论中，您提到数据逐个传入，而不是一次性传入。但是Array.prototype.sort()每次都必须重新整理整个数组，即使它已经大部分排好序了；只有一些元素没有在它们应该的位置上。

对于您这种情况，我倾向于使用插入排序，而不是 JavaScript 内置的排序方法（通常是引擎的变体之一合并排序或快速排序）。插入排序并不是一个很好的通用排序算法，但当你只需要把几个项目添加到已经排序好的数组中时，它是很好的选择。这正是您在这里所做的，听起来很合适。

这是算法的基本实现。

/**
 * Compare two items as though they were strings.
 *
 * This is like the default comparison for Array.prototype.sort()
 *
 * @param {*} a The first item
 * @param {*} b The second item
 *
 * @return -1 if a is less, 1 is b is less, 0 otherwise
 */
function compareStrings(a, b) {
    var sa = String(a),
        sb = String(b);

    if (sa < sb) {
        return -1;
    }
    if (sa > sb) {
        return 1;
    }
    return 0;
}

/**
 * Insert a new item into a sorted array.
 *
 * The compareFunction callback function works as for the analogous argument
 * in Array.prototype.sort(). Leave unspecified to compare lexically.
 *
 * @param {Array}     data            A sorted array, into which to put this item
 * @param {*}         newItem         The item to add to the data.
 * @param {Function=} compareFunction Optional comparison function.
 */
function arrayInsert(data, newItem, compareFunction) {
    var stop = data.length,
        i = 0;

    compareFunction = compareFunction || compareStrings;
    while (i < stop) {
        if (compareFunction(newItem, data[i]) < 0) {
            data.splice(i, 0, newItem);
            return;
        }
        i += 1;
    }
    // If we got this far, then this should be the last item.
    data.push(newItem);
}

当页面加载时，整个数组仍然需要排序一次，并且不应该使用插入排序（最好让服务器发送已经排序好的数据，但如果无法这样做，则使用普通的Array.prototype.sort函数）。然后，当您获得新数据时，对于每个新数据项，请调用arrayInsert(data, newItem,/*您的比较函数*/)。这应该可以加快速度。

如果这仍然太慢，那么您可以将新数据项放入队列中，并在页面上添加一个短定时器。每隔几毫秒钟，该计时器检查队列，如果有任何等待的项目，则将其中一个添加到数组中。这实际上不会使事情更快（事实上，它会使它们稍微慢一些），但页面不应再冻结。

- The Spooniest

Answer 2

不要先推送再排序，我建议使用二分查找来确定应该插入新对象的索引。

以下代码没有额外开销，因为没有函数调用。

此外还有一个变量iteration，它只是作为证人，你可以扔掉它。

我在jsfiddle上制作了以下代码的演示

假设你的a已经排序并包含唯一位置，你可以这样做

// THIS SECTION IS ONLY THERE TO SUIT YOUR CONSTRAINTS (100 objects in a)
var a = [];

for (var i = 0; i < 200; i++) {
    if (i & 1) {
        a.push({ id: i, position: i }); // objects are pushed only if they position is odd
    }
}

// this means o.position (our new object) can have any even value, we know that it won't already exist in a
var o = {
    id: 2,
    position: 2
};
var start = 0,
    end = (a.length - 1),
    mid = end >>> 1,
    left,
    right;

var iterations = 0;

while (mid !== a.length - 1) {
    if (mid > 0) {
        leftIsMore = a[mid - 1].position > o.position;
    } else {
        leftIsMore = false;
    }

    rightIsLess = a[mid].position < o.position;

    if (!leftIsMore && !rightIsLess) {
        break;
    } else if (leftIsMore) {
        end = mid - 1;
    } else {
        start = mid + 1;
    }

    mid = (start + end) >>> 1;
    iterations++;
}

var index = mid;

if (index === a.length - 1) {
    a.push(o);
} else {
    a.splice(index, 0, o);
}

console.log(a, 'Number of iterations to insert: ', iterations);

- axelduch

Answer 3

你可以自己实现一些非常高效的排序算法，例如快速排序和归并排序。

在这篇有趣的文章中，您可以找到JavaScript sort()和MergeSort实现之间的比较。我建议你更多地了解排序算法，并找到适合你问题的那一个。

- Emily

---

不需要优化内置的排序算法。它可以在几分之一秒内对数十万个元素进行排序。 - Butt4cak3