javascript - 通过在 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”属性上执行内置“排序”函数的 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其中包含三种算法中每一种的代码。

算法一是拼接，然后对拼接后的数组进行排序。在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/