获取排序整数数组的索引

Question

我有一个包含整数的数组，需要对其进行排序。但是，结果不应该包含整数值，而应该包含索引。即旧数组的新顺序。

例如: 10，20，30

结果应该是: 2，1，0

什么是实现这一目标的优化算法？

Answer 1

如果您将每个元素转换为(value, position)的元组并对其进行排序，则可以使用任何排序算法来实现这一点。

也就是说，[10, 20, 30]将变成[(10, 0), (20, 1), (30, 2)]。然后使用一个比较器对该数组进行排序，该比较器会查看元组的第一个元素，从而得到[(30, 2), (20, 1), (10, 0)]。从这里，您可以简单地获取每个元组的第二个元素，以获得您想要的内容，即[2, 1, 0]。(假设您想要反向排序。)

Answer 2

不会与任何其他排序算法不同，只需修改它，使其构建或接受一个索引数组，然后操作数据和索引数组，而不仅仅是数据。

Answer 3

您可以创建一个指向原始整数数组的指针数组，执行合并排序或任何您认为最适合的排序算法(使用指针处的值)，然后向下运行列表，根据每个指针相对于包含原始整数数组的已分配块的开头的地址计算索引。