algorithm - 确定数字列表的顺序(可能不需要排序)

Question

我有一个任意顺序的唯一整数数组(例如 val[i])，我想填充另一个数组(ord[i])与整数的排序索引。换句话说，val[ord[i]] 按照 i 递增的顺序排列。

现在，我只是用 0, ..., N 填充 ord，然后根据值数组对其进行排序，但我想知道我们是否可以更有效地处理 code>ord 开始时未填充。这更多是出于好奇而提出的问题；我真的不关心必须预填充列表然后对其进行排序的额外开销(它很小，我使用插入排序)。这可能是一个答案很明显的愚蠢问题，但我在网上找不到任何东西。

Answer 1

就时间复杂度而言，没有比排序更快的方法了。如果有，那么您可以使用它来更快地排序:生成索引，然后使用它们对原始数组重新排序以使其按排序顺序排列。这种重新排序将花费线性时间，因此总体而言您将拥有更快的排序算法，从而产生矛盾。