c - 如何获取整数数组的降序（序数）？

Question

我需要在整数数组中找到元素的降序。

例子：

如果我有一个数组：

x = {24, 55, 22, 1}

我想要一个 C 中的算法，它产生数组order，其中：

order = {2, 1, 3, 4}

考虑到“我的”数组x可能会变得相当大（从 1k-1M），我的问题如下：如何order尽可能高效（快速）地获得数组？显然必须存在一个有效的算法来做到这一点？

Answer 1

我想更有效的方法是最知名的方法。例如：

• 为从 0 到 N-1 的所有索引分配一个向量并初始化它
• 使用一种有效的排序算法对索引向量进行排序，例如快速排序或合并排序，但通过引用原始数据向量（您对索引进行排序，您比较原始数据）

Answer 2

您可以使用 qsort 标准函数的比较器功能： http ://www.tutorialspoint.com/c_standard_library/c_function_qsort.htm 只需实现您的比较器以添加间接，即替换：

return ( *(int*)a - *(int*)b );

经过

return (x[*(int*)b] - x[*(int*)a]);

（编辑以获得降序）

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

int x[] = { 88, 56, 100, 2, 25 };
int indexes[] = { 0, 1, 2, 3, 4};

int cmpfunc (const void * a, const void * b)
{
   return ( x[*(int*)b] - x[*(int*)a] );
}

int main()
{
   int n;

   printf("Before sorting the list is: \n");
   for( n = 0 ; n < 5; n++ ) {
      printf("%d ", indexes[n]);
   }

   qsort(indexes, 5, sizeof(int), cmpfunc);

   printf("\nAfter sorting the list is: \n");
   for( n = 0 ; n < 5; n++ ) {
      printf("%d ", indexes[n]);
   }

  return(0);
}

Answer 3

我将从 stdlib.h 中的qsort开始，因为它需要一个指向函数的指针，不会是最快的，但肯定更容易编码。

int v[4] = {24, 55, 22, 1};
int fcmp(const void *a, const void *b) {
    int A = *(const int*)a;
    int B = *(const int*)b;
    if (v[A] > v[B]) return -1;
    if (v[A] < v[B]) return +1;
    return 0;
}

int main(int argc, char *argv[])
{
    int r[4] = {0, 1, 2, 3 };
    qsort(r, 4, sizeof(int), fcmp);
}