排序松散连接的数据，使人联想到单链表

Question

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

--这是上下文：

程序返回一个对象数组，每个对象包含两个变量: id和previous_id。id是唯一的标识符，previous_id引用数组中对象的另一个id。数组中对象的顺序是随机的。

显而易见的排序当然是这样的:在排序数组中，第一个对象是previous_id为null的对象。数组中的下一个对象应该始终是其previous_id与当前对象的id相对应的对象，或者是最后一个对象。

，按上述顺序排序这些变量的有效算法是什么？

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

我目前的算法过于复杂，其工作方式如下：

• 首先，我们通过构建数组的哈希映射来为排序做好准备。hashmap是通过迭代数组并将键映射到当前对象的id并将值映射到当前对象，并封装在大小为1的数组中构建的。

这些数组的目标是始终保持正确的顺序， 除了第一个元素之外，它可以有一个previous_id，该元素可以指向它自己的数组中不存在的元素，或者是null。 在哈希映射中指向此数组的键始终是数组中最后一个元素的id。

• 然后继续遍历hashmap，直到hashmap的长度小于或等于1为止。
• 在循环中，我们遍历hashmap。
• 如果当前哈希项的键为null，我们将使用数组的第一个元素调用head。我们还使用数组的最后一个元素，我们称之为对接。
• 现在，我们可以将两个数组合并为一个数组，方法是将在散列映射中找到的数组(其键等于头的previous_id )与迭代中的当前数组合并，并删除hashmap中找到的数组。

伪码是这样的：

$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)算法。我觉得应该有更简单的方法。

答案已张贴在下面。我决定为未来的访问者包括它的php实现：

$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)相比，具有很高的计算效率。