对随机数的索引进行排序

Question

通过这种方式，我可以找到随机数字的索引并存储它们。

示例：

300，2，43，12，0，1，90

Values  ->  0  1  2  12  43  90  300
Indexes ->  0  1  2  3   4   5   6

所以。我可以存储它们的索引而不是我的值吗？

像这个

300  2  43  12  0  1  90
6   2  4   3   0  1  5

负数也可能吗？

Answer 1

编辑：(更正我之前发布的错误解决方案(

#include <stdio.h>
#include <stdlib.h>
typedef struct {
int val;
int in0;
int in1;
} pair_t;
int cmpVal( const void *a, const void *b ) { return ((pair_t*)a)->val - ((pair_t*)b)->val; }
int cmpOrg( const void *a, const void *b ) { return ((pair_t*)a)->in0 - ((pair_t*)b)->in0; }
int main() {
int i;
int unsort[] = { 300, 2, 43, 12, 0, 1, 90 };
const int n = sizeof unsort/sizeof unsort[0];
// Make a copy in unsorted order including orginal sequence.
pair_t *worken = malloc( n * sizeof *worken );
for( i = 0; i < n; i++ )
worken[i].val = unsort[i], worken[i].in0 = i;
// Sort by value ascending
qsort( worken, n, sizeof pair_t, cmpVal );
// Register this sequence with each element
for( i = 0; i < n; i++ )
worken[i].in1 = i;
// Restore original sequence
qsort( worken, n, sizeof pair_t, cmpOrg );
// Copy the indices (of sorted version) to 'persistant' array.
int sorted[n] = { 0 };
for( i = 0; i < n; i++ )
sorted[i] = worken[i].in1;
// Toss 'working' buffer.
free( worken );
// List original sequence
for( i = 0; i < n; i++ )
printf( "%4d", unsort[ i ] );
putchar( 'n' );
// List corresponding indices (as if sorted)
for( i = 0; i < n; i++ )
printf( "%4d", sorted[ i ] );
putchar( 'n' );
return 0;
}

输出

300   2  43  12   0   1  90
6   2   4   3   0   1   5

为清晰起见，省略了原始数组中"replace values with indices"的琐碎分配循环。。。

编辑#2：

OP建议将未排序的数组的值(！(替换为指示排序顺序的索引。

以下内容做得同样多，前提是数组值不接近ints的值的顶端。

#include <stdio.h>
#include <limits.h>
void show( int u[], size_t cnt ) { // Show current array values
for( size_t i = 0; i < cnt; i++ )
printf( "%4d", u[ i ] );
putchar( 'n' );
}
void oddSort( int u[], size_t cnt ) {
show( u, cnt );
// Succesively find and replace highest values with decreasing large int values.
int peak = INT_MAX;
for( size_t set = 0; set < cnt; set++ ) {
int maxID = 0;
while( u[maxID] >= peak ) maxID++; // find first non-replaced value
for( size_t i = maxID + 1; i < cnt; i++ )
if( u[i] < peak && u[i] > u[maxID] )
maxID = i;
u[maxID] = peak--;
}
// transpose down to 0, 1, 2...
for( size_t i = 0; i < cnt; i++ )
u[i] -= peak + 1;
show( u, cnt );
}
int main() {
{
int u[] = { 300, 2, 43, 12, 0, 1, 90 };
oddSort( u, sizeof u/sizeof u[0] );
}
putchar( 'n' );
{
// Test with negatives (coincidentally lowest value in first pos)
int u[] = { -256, 300, 2, 43, 12, 0, 1, 90 };
oddSort( u, sizeof u/sizeof u[0] );
}
return 0;
}

输出：

300   2  43  12   0   1  90
6   2   4   3   0   1   5
-256 300   2  43  12   0   1  90
0   7   3   5   4   1   2   6