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

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

(注释)我需要的是一个未排序数组的索引,就像它们按升序排序一样.

您也可以使用步骤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]