algorithm - 确定哪个排序排列对数组进行排序

Question

所以给定数组 A = [3,2,6]，其中 A[1]= 3，A[2] = 2，A[3] = 6，排序后我们有 A=[2,3,6 ]，给出排列 P = [2,1,3]。

返回这个数组 P 的算法是什么(越快越好)？

我正在考虑让未排序数组 A 中的每个元素成为一对，索引作为该对的第二个元素。我将制作一个列表并填写元组。在我按值对列表进行排序后(使用某种稳定的排序)，索引将相应地移动以提供正确的数组 P。这是继续进行的正确方法，还是有更好的方法？

Answer 1

最简单的方法(在大多数编程语言中)是构造一个索引数组，然后使用比较器中的原始数组对它们进行排序。

例如，在 Python 中:

A = [3, 2, 6]
sorted(range(3), key=lambda i: A[i])

output:
[1, 0, 2]

请注意，这里的索引在您的问题中是基于 0 而不是基于 1，因此输出是 [1, 0, 2] 而不是 [2, 1, 3 ]。当前的编程语言很少有从 1 开始的索引，尽管有一些。

你建议用索引装饰输入，对其进行排序，然后删除原始值也很有效，尽管我个人更喜欢像第一种方法那样直接对索引进行排序。

[j for _, j in sorted(zip([3, 2, 6], range(3)))]