按照其相对位置排序数组

Question

示例对象数组：

[{
    id: 'a',
    beforeId: null
}, {
    id: 'b',
    beforeId: 'c'
}, {
    id: 'c',
    beforeId: 'a'
}, {
    id: 'd',
    beforeId: 'b'
}]

输出顺序：d-b-c-a；每个元素都根据其beforeId属性相对于其他元素排序。

我可以创建一个临时数组并对上述数组进行排序。使用array.sort命令是否可行？

- Shyamal Parikh

---

@scagood 不对。1）回调函数应该返回<0、0或>0，而不是布尔值。2）这不是这里的标准。（我承认你需要反复看一遍才能看到它，但这个问题还不错。） - deceze

基本上是从右边开始排序。具有 beforeId 'null' 的元素将成为最后一个元素，所有其他元素将从该元素找到它们的顺序。我正在尝试使用 charCodeAt() 将字符串转换为可以用于排序的数字，但这不会是漂亮的代码。我们将使其正常工作，但我强烈建议找到更好的排序机制。 - Shilly

一个常规的排序函数在这里没有用处，因为通过检查前两个项目，无法确定它们的顺序。每个项目仅与其直接邻居相连，但排序不是以这种方式工作的。 - axiac

@scagood 我已经尝试让它更明显了...它就在名称中：before id。 - deceze

看起来你有一个“有向无环图”。 - T Tse

Answer 1

你可以使用关系构建对象，并通过使用beforeId: null的对象生成结果，并将所有对象推入结果数组中。

下一个对象是具有实际val作为键的对象。

复杂度：O(2n)。

function chain(array) {
    var o = {}, pointer = null, result = [];

    array.forEach(a => o[a.beforeId] = a);

    while (o[pointer]) {
        result.unshift(o[pointer]);
        pointer = o[pointer].val;
    }

    return result;
}

var data = [{ val: 'a', beforeId: null }, { val: 'b', beforeId: 'c' }, { val: 'c', beforeId: 'a' }, { val: 'd', beforeId: 'b' }];

console.log(chain(data));

.as-console-wrapper { max-height: 100% !important; top: 0; }

- Nina Scholz

---

在我的环境中，这个比原来的快了十倍以上（测试链接：https://gist.github.com/scagood/097295617c204f06728e1fa5c9393f8c）。 - scagood

Answer 2

这是一个非常低效和幼稚的算法，但它可以工作：

const array = [
    {id: 'a', beforeId: null},
    {id: 'b', beforeId: 'c'},
    {id: 'c', beforeId: 'a'},
    {id: 'd', beforeId: 'b'}
];

// find the last element
const result = [array.find(i => i.beforeId === null)];

while (result.length < array.length) {
    // find the element before the first element and prepend it
    result.unshift(array.find(i => i.beforeId == result[0].id));
}

console.log(result);

- deceze

Answer 3

数组可以使用array.sort进行排序吗？

当然可以，需要使用一个辅助函数：

graph = [
    {id: 'a', beforeId: null},
    {id: 'b', beforeId: 'c'},
    {id: 'c', beforeId: 'a'},
    {id: 'd', beforeId: 'b'}
];

let isBefore = (x, y) => {
    for (let {id, beforeId} of graph) {
        if (id === x)
            return (beforeId === y) || isBefore(beforeId, y);
    }
    return false;
};

graph.sort((x, y) => x === y ? 0 : (isBefore(x.id, y.id) ? -1 : +1))

console.log(graph);

isBefore 如果 x 立即或者传递性地在 y 之前返回 true。

对于一般的、非线性的拓扑排序，请参见 https://en.wikipedia.org/wiki/Topological_sorting#Algorithms

更新：如 此处 所示，这种方法效率极低，因为 sort 包含很多不必要的比较。这里是目前最快的版本：

function sort(array) {
    let o = {}, res = [], len = array.length;

    for (let i = 0; i < len; i++)
        o[array[i].beforeId] = array[i];

    for (let i = len - 1, p = null; i >= 0; i--) {
        res[i] = o[p];
        p = o[p].id;
    }

    return res;
}

这是@Nina的想法，针对速度进行了优化。

- georg

Answer 4

你可以尝试这种方法：

// order(null, vals, []) = ["d", "b", "c", "a"]
function order(beforeId, vals, result){
    var id = beforeId || null;

    var before = vals.filter(function(val){
                return val.beforeId ===  id
    });

    if (before.length === 0) return result;   

    return order(before[0].val,
                    vals, 
                [before[0].val].concat(result));
}

- Dhananjaya Kuppu