对松散连接的数据进行排序，让人联想到单链表

Question

我正在寻找排序链接数据的有效解决方案。

这是上下文：

一个程序returns一个对象数组，每个对象包含两个变量：id 和previous_id。 id 是唯一标识符，previous_id 指的是数组中对象的另一个 id。数组中对象的顺序是随机的。

明显的排序当然是这样的：在排序数组中，第一个对象是 previous_id 为空的对象。数组中的下一个对象应该总是 previous_id 与当前对象的 id 对应的对象，或者它是最后一个对象。

按照上述顺序对这些变量进行排序的有效算法是什么？

我的直觉表明有一种简单的方法可以对这些变量进行排序。这些对象的表示方式让我想起了单向链表。然而我似乎找不到一个优雅的解决方案。

我目前的算法过于复杂，工作原理如下：

首先，我们通过构建一个散列映射来准备要排序的数组阵列。哈希图是通过遍历数组和映射来构建的当前对象id的键和当前对象的值对象，包裹在大小为 1 的数组中。

The goal of these arrays is to always have the correct ordering,
except the first element, which can have a previous_id that may point to an element which is not in it's own array, or be null.

The key pointing to this array in the hash map is always the id of the last element in the array.

然后我们继续遍历 hashmap 直到 hashmap 的长度小于或等于 1.
在循环中我们遍历 hashmap。
如果当前hash项的key不为null，取第一个我们将称之为 head 的数组元素。我们还取数组的最后一个元素，我们称之为 butt。
我们现在可以将两个数组合并为一个数组，方法是在迭代中将哈希映射中找到的数组的键等于头部的 previous_id 与当前数组并删除找到的数组在哈希图中。

伪代码是这样的：

$tbr = $this->prepareDataForSorting();
while (count($tbr) > 1) {
    foreach ($tbr as $key => $children) {
        $head = array_first($children);
        if ($head->previousId !== null) {
            $butt = array_last($children);
            $tbr[$butt->id] = array_merge($tbr[$head->previousId], $children);
            unset($tbr[$head->previousId]);
        }
    }
}
return $tbr[array_key_first($tbr)];

排序准备过程是这样实现的：

$tbr = [];
foreach ($this->children as $child) {
    $tbr[$child->id] = [$child];
}
return $tbr;

我对这个算法的问题是它根本不是轻量级的。它需要哈希映射作为辅助数据结构以及 O(n^2) 算法。我觉得应该有更简单的方法。

The answer has been posted below. I decided to include it's php implementation for future visitors:

$mapping = $this->mapData();
$current = $mapping[null] ?? null;
$tbr = [];
while ($current !== null) {
    $tbr[] = $current;
    $current = $mapping[$current->id] ?? null;
}
return $tbr;

有地图数据：

$tbr = [];
foreach ($this->children as $child) {
    $tbr[$child->previousId] = [$child];
}
return $tbr;

简直太美了

Answer 1

你可以用更好更简单的方式实现你想要的。我的建议如下：

创建哈希映射
迭代数组并为数组中的每个条目在哈希映射中创建一个条目，其键和值分别为 previous_id 和迭代中的当前条目。
最后，你需要获取键null的散列值（因为你的第一项的previous_id为null），将其值推送到最终数组，并使用id的当前条目作为 hashmap 的新键。
做最后一步，直到最终数组的长度与原始数组的长度相同。

这种方法的复杂度为 O(n)，与 O(n^2)

相比非常有效

对松散连接的数据进行排序，让人联想到单链表

Sorting loosely connected data reminiscent of a singly linked list

php

arrays

sorting

computer-science

singly-linked-list

我正在寻找排序链接数据的有效解决方案。