0

我有一个由数组组成的 JavaScript“表”，其中“行”由共享相似结构的对象组成（成员属性类似于形成“列”，其值为“单元格”）。

该表已通过以相反顺序应用的合并排序以级联方式对一个或多个列进行排序，并且可以是 20 - 20,000 行长的任何地方。

用于在正确位置将新行插入表中而不重新排序整个表（或者更确切地说，找到新行的插入索引）的最佳算法是什么？

这方面的一个例子是：

Sort Order = name, id

id    name    description
0     a       blah
1     b       foo
2     d       blah
3     d       blah 2
...
19    d       blah 18

Insert:

id    name    description
20    c       bar

To Yield:

id    name    description
0     a       blah
1     b       foo
20    c       bar
2     d       blah
3     d       blah 2
...
19    d       blah 18

（对不起所有引用的定义，当我第一次尝试问这个问题时，人们似乎很困惑，认为“表”指的是 SQL 数据库表或类似的）

4

1 回答 1

0

为有兴趣的人解决了以下问题：

var table = [
    {i: 0, id: 0, id2: 0, id3: 0},
    {i: 1, id: 0, id2: 1, id3: 0},
    {i: 2, id: 1, id2: 0, id3: 0},
    {i: 3, id: 1, id2: 2, id3: 0},
    {i: 4, id: 1, id2: 3, id3: 0},
    {i: 5, id: 2, id2: 0, id3: 1},
    {i: 6, id: 2, id2: 0, id3: 2},
    {i: 7, id: 2, id2: 1, id3: 0},
    {i: 8, id: 2, id2: 1, id3: 1},
    {i: 9, id: 2, id2: 2, id3: 0}
    ];

var sort = ['id', 'id2'];

function InsertionIndex(table, sort, row) {
    var state = {
        _compare: function (left, right) {
            if (left < right) { return (1); }
            else if (left > right) { return (-1); }
            return (0);
        },
        column: '',
        max: table.length,
        min: 0,
        row: row,
        _search: function (state) {
            var minc = this._compare(this.table[this.min][this.column], state.row[this.column]);
            var maxc = this._compare(this.table[this.max - 1][this.column], this.row[this.column]);
            if (state.table[state.min][state.column] == state.table[state.max - 1][state.column]) { return; }
            if (minc < 0) { state.max = state.min; return; }
            if (maxc > 0) { state.min = state.max; return; }
            if ((state.max - state.min) > 2) {
                var mid = Math.ceil((state.min + state.max) / 2);
                var midc = state._compare(state.table[mid][state.column], state.row[state.column]);
                if (midc < 0) {
                    state.max = mid;
                    state._search(state);
                    return;
                } else if (midc > 0) {
                    state.min = mid;
                    state._search(state);
                    return;
                } else {
                    for (var i = mid - 1; i >= state.min; i--) { if (state._compare(state.table[i][state.column], state.row[state.column]) != 0) { state.min = i + 1; break; } }
                    for (var i = mid + 1; i < state.max; i++) { if (state._compare(state.table[i][state.column], state.row[state.column]) != 0) { state.max = i; break; } }
                    return;
                }
            } else {
                if (maxc < 0) {
                    if (minc > 0) { state.min = state.max - 1; state.max = state.max - 1; return; }
                    else { state.max = state.max - 1; return; }
                } else if (minc > 0) {
                    state.min = state.max - 1; return;
                }
            }
            return;
        },
        table: table
    };
    for (var i = 0; i < sort.length; i++) {
        state.column = sort[i];
        state._search(state);
        if (state.min >= state.max) { break; }
    }
    return ({ max: state.max, min: state.min });
}

for (var i = 0; i < table.length; i++) {
    document.write(table[i].i + '&nbsp;&nbsp;&nbsp;&nbsp;' + table[i].id+ '&nbsp;&nbsp;&nbsp;&nbsp;' + table[i].id2 + '&nbsp;&nbsp;&nbsp;&nbsp;' + table[i].id3 + '<BR />');
}
var insertion = {i: 3, id: 0, id2: 1, id3: 1};
document.write(InsertionIndex(table, sort, insertion).min + '&nbsp;&nbsp;&nbsp;&nbsp;' + InsertionIndex(table, sort, insertion).max + '&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1&nbsp;&nbsp;&nbsp;&nbsp;2<BR />');
insertion = {i: 3, id: 1, id2: 1, id3: 1};
document.write(InsertionIndex(table, sort, insertion).min + '&nbsp;&nbsp;&nbsp;&nbsp;' + InsertionIndex(table, sort, insertion).max + '&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;3&nbsp;&nbsp;&nbsp;&nbsp;3<BR />');
insertion = {i: 3, id: 2, id2: 1, id3: 1};
document.write(InsertionIndex(table, sort, insertion).min + '&nbsp;&nbsp;&nbsp;&nbsp;' + InsertionIndex(table, sort, insertion).max + '&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;7&nbsp;&nbsp;&nbsp;&nbsp;9<BR />');
insertion = {i: 3, id: 3, id2: 1, id3: 1};
document.write(InsertionIndex(table, sort, insertion).min + '&nbsp;&nbsp;&nbsp;&nbsp;' + InsertionIndex(table, sort, insertion).max + '&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;10&nbsp;&nbsp;&nbsp;&nbsp;10<BR />');
于 2013-05-02T03:19:13.807 回答