在javascript中加入对象数组是否更有效地排序或插入？

Question

我有一个名为“num”的字段的多个对象。Num 可以是 1000000000 到 10000000005 之间的任何数字。我想确保如果我有 x 个列表，所有列表都需要根据“num”属性按升序排列在 array1 中。

如果我从这样的数组开始“

array1": [{item:23532532, num:1000000520},{item:23523, num:1000000620},{item:346346432, num:1000000620}]

我有第二个数组

"array2": [{item:23532, num:....},{item:3623, num:....}]

假设 array2 按“num”排序，是否更有效：

1）添加然后整个排序 - 循环遍历“array2”中的每个项目并将其添加到“array1”的末尾，然后在整个数组的“num”属性上执行内置“sort”函数的javascript？

2) Insert Into Right Place - 循环遍历“array2”中的每一项并使用“if”条件来检查“num”值是否大于“array2”中的当前项，如果是，则插入之前的元素该索引通过“拼接”。（没有使用 javascript 内置数组排序）

或者有没有更有效的方法？伪代码或示例代码是一个加号。

Answer 1

我在三种不同的浏览器中测量了三种不同算法的结果。

关于所有与性能相关的问题，有两点是正确的：

1. 如果您真的想知道答案，则必须在多个浏览器中测试您的特定算法才能真正回答问题。

2. 许多与性能相关的问题在使用它们的给定上下文中实际上并不重要，因此担心它们直到您知道需要担心它们无非是浪费时间在过早的优化甚至不必要的优化上。因此，在处理特定的性能领域之前，您应该知道它很重要，并且知道它值得花时间。

也就是说，这里是对三种算法的一些测量。这假设您从两个对象数组开始，每个数组都按每个对象中存在的一个特定数字属性独立排序。

这是 jsperf：http : //jsperf.com/concat-sort-vs-insert-sort/5 ，其中包含三种算法中每一种的代码。

算法 1 进行连接，然后对连接后的数组进行排序。 在 JS 中，无非是：

var result = arr1.concat(arr2);
result.sort(sortByNum);

算法 2 是一种插入排序的尝试。 基本思想是遍历第二个数组，并为该数组中的每个项目找到将其插入第一个数组的位置。由于两个数组都已排序，因此我们只需要在插入最后一项之后的位置开始寻找将下一项插入到第一个数组中的位置。

算法 3 是归并排序。 这里的想法是创建一个空的结果数组和两个索引，两个源数组中的每一个都有一个索引。对于每个源索引处的值，您将两个项中较低的项推入结果，然后增加其源索引。当任一源索引用完时，您将推入另一个数组的其余部分。我猜它会比插入排序更有效，因为它不必将项目插入数组的中间，只需添加到末尾，这可能是一个更快的操作。

为了运行测试，我创建了两个数组，每个数组包含 100 个对象。每个对象都有一个数值属性，该属性被分配了一个介于 0 和 100,000 之间的随机数。然后对两个源数组中的每一个进行预排序。然后在这两个源阵列上测试每个算法。

而且，这里是结果：

下面是归并排序算法的代码：

function mergeSort(arr1, arr2) {
    var result = [];
    var index1 = 0;
    var index2 = 0;
    if (!arr1.length) {
        return arr2.slice(0);
    } else if (!arr2.length) {
        return arr1.slice(0);
    }
    while (true) {
        if (arr1[index1].num <= arr2[index2].num) {
            result.push(arr1[index1]);
            ++index1;
            // see if we reached the end of the array
            if (index1 >= arr1.length) {
                result.push.apply(result, arr2.slice(index2));
                break;
            }
        } else {
            result.push(arr2[index2]);
            ++index2;
            // see if we reached the end of the array
            if (index2 >= arr2.length) {
                result.push.apply(result, arr1.slice(index1));
                break;
            }
        }
    }
    return result;
}

工作演示：http : //jsfiddle.net/jfriend00/mja1c13d/