考虑以下对象数组:
[
{v: 'a'},
{v: 'b'},
{v: 'c', ptr: 'b'},
{v: 'd', ptr: 'a'},
{v: 'e'},
]
一些对象包含ptr
属性,引用v
它应该直接位于前面的对象的属性值。两个对象永远不会尝试直接位于同一个对象之前,并且数组中永远不会出现循环(例如 a->b->c->a)。
因此,这里有两种可能的有效的对象重新排列:
[
{v: 'e'},
{v: 'd', ptr: 'a'},
{v: 'a'},
{v: 'c', ptr: 'b'},
{v: 'b'},
]
[
{v: 'c', ptr: 'b'},
{v: 'b'},
{v: 'd', ptr: 'a'},
{v: 'a'},
{v: 'e'}
]
ptr
如果没有属性引用对象,则对象出现在输出中的位置并不重要。重要的是,当ptr
属性要求时,某些对象直接位于其他对象之前。
执行这种重新排列的相当有效的算法是什么?
尽管保证数据不包含循环,但重新排列时应小心,不要进入无限循环,从而永远重新排列对象。
请注意,虽然这些示例使用 和 的字符串v
,但ptr
实际应用程序将涉及 DOM 元素作为v
和 的值ptr
引用。因此,解决方案应该只能比较v
和ptr
属性是否相等。