随机数的排序索引

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

如果您愿意使用一系列“助手”，这可以简单地完成

struct

s...

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int val;
    int in0;
    int in1;
} pair_t;

// Two qsort() comparison functions
// NB: these may cause integer overrun for very large values
// OP advised to use longer 'comparison' evaluations if required
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( void ) {
    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 original sequence.
    pair_t *worken = malloc( n * sizeof *worken );
    for( i = 0; i < n; i++ )
        worken[i].val = unsort[i], worken[i].in0 = i;

    // Sort that array by value ascending
    qsort( worken, n, sizeof pair_t, cmpVal );

    // Register this sequence with each array element
    for( i = 0; i < n; i++ )
        worken[i].in1 = i;

    // Restore array's original sequence
    qsort( worken, n, sizeof pair_t, cmpOrg );

    // Copy the indices (of sorted version) to 'persistent' array.
    // for demo, using a separate array instead of overwriting original
    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

为了清楚起见，省略了“用索引替换原始数组的值”的简单赋值循环......

---

OP 建议将未排序的数组的值替换（！）为指示排序顺序的索引。 （这意味着，不使用额外的内存分配。）

以下内容的作用与此相同，但前提是数组值不接近

int

值的顶端 (

INT_MAX

)。
对于

n

整数数组，这会盲目使用

INT_MAX - n + 1

到

INT_MAX

的值来达到其目的。

此版本是处理器密集型的，因为它对数据数组进行多次传递。

#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 );

    // Successively 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( void ) {
    {
        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