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

EN

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

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]

“快速”意味着插入(当然还有查找)需要一个复杂度为O(log )的排序数据结构。所以二叉树就行了。

您可以将索引创建为一个位置数组，并按照现有顺序初始化它: idx=0，1，2，.，n-1。

然后使用您最喜欢的排序算法对索引数组进行排序，但是每当执行比较时，您都会使用这些值作为引用原始数组的位置，而不是直接比较它们。例如，要比较项目i和j，可以执行cmp(arr[idxi]，arr[idxj])而不是cmp(idxi，idxj)。