arrays - 创建未排序数组索引的最快方法

Question

我正在处理一个未排序数组的问题。我需要处理这个数组以生成一个索引数组，就好像它是按升序排序的一样。

示例 1:

假设我有一个未排序的数组 [9, 7, 8, 6, 12]

作为输出，我需要一个索引数组 [3, 1, 2, 0, 4]。

示例 2:

未排序数组:[10, 9, 11, 8, 12] 索引数组应该是:[ 2, 1, 3, 0, 4]

截至目前，我正在做的就像老式的“冒泡排序”一样，我正在比较每一种可能性。我想知道让它变快的方法。

Answer 1

如果您不担心额外的空间，请执行以下操作:

1. 制作一个数组对 (value, index)
2. 按升序对值(第一个成员)进行排序
3. 从已排序的对数组中获取索引(第二个成员)

以您的数据为例，您会得到:

[{9,0}, {7,1}, {8,2}, {6,3}, {12,4}] // Step 1
[{6,3}, {7,1}, {8,2}, {9,0}, {12,4}] // Step 2
[   3,     1,     2,     0,      4 ] // Step 3

(comment) I need is index of an unsorted array as if they were sorted in ascending order.

您也可以使用第 3 步中的数组来生成此输出。使用你的第二个例子，你得到这个:

[{10,0},  {9,1}, {11,2},  {8,3}, {12,4}]
[ {8,3},  {9,1}, {10,0}, {11,2}, {12,4}]
[    3,      1,      0,      2,      4 ]

现在创建输出数组，遍历索引数组(即 [3,1,0,2,4])并将每个项目的索引设置到由值，即索引 3 会得到 0，因为 3 在索引 0 处，索引 1 会得到 1，因为 1 在 1 处，索引 0 会得到 2，因为 0 在 2 处，依此类推。

这是附加步骤的说明:

int position[] = {3, 1, 0, 2, 4};
int res[5];
for (int i = 0 ; i != 5 ; i++) {
    res[position[i]] = i;
}

这会产生以下数组:

[2, 1, 3, 0, 4]