如何计算C中向量的等级？

Question

如何(有效/快速)确定C中矢量(元素)的排名(不是C++或使用非标准库)？例如,矢量的等级(ing)x=(0.25, 0.54, 0.38, 0.32, 0.49, 0.06, 0.41, 0.21, 0.98, 0.23)应该是rank(x)=(4, 9, 6, 5, 8, 1, 7, 2, 10, 3).

顾名思义,"排名"给出了向量的每个元素与向量的所有其他元素相关的等级.因此,rank(x[k])=l意味着k第th个元素x是l所有元素中的最小元素x(例如,k=6在上面的示例中,l为1,即,x的第6个元素是最小的).请注意,这样的函数rank()存在于其他几种编程语言中,但我还没有看到过C实现.我正在寻找的是一个纯C实现,它对整数或实数的向量尽可能快地工作.

Answer 1

一种方法是将数据与索引配对,使用排序qsort和仅检查值并忽略索引的比较器,然后根据排序的索引分配排名.

这是一个malloc临时数组对的实现,而不是使用自动存储.当数据量足够大以超出堆栈时,这会更安全.

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

struct rank_pair {
    double val;
    size_t ind;
};

int cmp_rank_pair(const void* a, const void* b) {
    struct rank_pair *lhs = (struct rank_pair*)a;
    struct rank_pair *rhs = (struct rank_pair*)b;
    return lhs->val < rhs->val ? -1 : (lhs->val > rhs->val ? 1 : 0);
}

void rank(double a[], int r[], size_t n) {
    struct rank_pair *tmp = malloc(n*sizeof(struct rank_pair));
    for (int i = 0 ; i != n ; i++) {
        tmp[i].val = a[i];
        tmp[i].ind = i;
    }
    qsort(tmp, n, sizeof(struct rank_pair), cmp_rank_pair);
    for (int i = 0 ; i != n ; i++) {
        r[tmp[i].ind] = i+1;
    }
    free(tmp);
}

int main(void) {
    const size_t N = 10;
    double a[] = {0.25, 0.54, 0.38, 0.32, 0.49, 0.06, 0.41, 0.21, 0.98, 0.23};
    int r[N];
    rank(a, r, N);
    for (int i = 0 ; i != N ; i++) {
        printf("%d\n", r[i]);
    }
    return 0;
}

演示.