javascript - 将json对象插入javascript中的有序数组

Question

我有一个 ~2000 对象的数组，格式如下:

[{
    "$order": 2998,
    "text": "Rosales Glenn",
    "id": 375
}, {
    "$order": 2999,
    "text": "Dillard Joyce",
    "id": 450
}, {
    "$order": 3000,
    "text": "Maryellen Hogan",
    "id": 365
}, {
    "$order": 3002,
    "text": "Jeannette Church",
    "id": 207
}]

我需要以一种高效的方式将一个对象插入到正确的位置:例如:

{
    "$order": 3001,
    "text": "Jeannette Chichi",
    "id": 205
}

假设我在插入新元素时不需要覆盖现有元素(没有重复的“$order”)，有谁知道使用 $order 作为键将新对象插入数组的快速好算法？外部库也是一个选项(如果它们支持 Angular)。谢谢!

Answer 1

至少你需要迭代直到找到索引。

var array = [{ "$order": 2998, "text": "Rosales Glenn", "id": 375 }, { "$order": 2999, "text": "Dillard Joyce", "id": 450 }, { "$order": 3000, "text": "Maryellen Hogan", "id": 365 }, { "$order": 3002, "text": "Jeannette Church", "id": 207 }],
    insert = { "$order": 3001, "text": "Jeannette Chichi", "id": 205 },
    index = -1;

array.some(function (a,i) {
    if (a.$order > insert.$order) {
        return true;
    }
    index = i;
});

array.splice(index + 1, 0, insert);

console.log(array);

或者按照建议，您可以对其使用二进制搜索。

function search(array, insert, cb) {
    var left = -1,
        right = array.length,
        actual;

    while (left !== right && left + 1 !== right) {
        actual = Math.floor((left + right) / 2);
        if (cb(array[actual]) < cb(insert)) {
            left = actual;
            continue;
        }
        if (cb(array[actual]) > cb(insert)) {
            right = actual;
        }
    }
    return left;
}

var array = [{ "$order": 2998, "text": "Rosales Glenn", "id": 375 }, { "$order": 2999, "text": "Dillard Joyce", "id": 450 }, { "$order": 3000, "text": "Maryellen Hogan", "id": 365 }, { "$order": 3002, "text": "Jeannette Church", "id": 207 }],
    insert = { "$order": 3001, "text": "Jeannette Chichi", "id": 205 },
    index = search(array, insert, function (a) { return a.$order; });

array.splice(index + 1, 0, insert);
console.log(array);