如何获取整数数组的降序（排名）？

Question

我需要找到一个整数数组中元素的降序排列。

例如：

如果我有一个数组：

x = {24, 55, 22, 1}

我希望您能提供一份用C语言编写的算法，其结果为数组order，其中：

order = {2, 1, 3, 4}

考虑到我的数组 x 可能会变得非常大（从1k-1M），我的问题如下：如何以尽可能高效（快速）的方式获取 order 数组？显然，必须存在一种有效的算法来实现这一点，对吗？

- userjuicer

---

“vector”是指数组吗？C++标准库中有一个名为“vector”的类型；而C语言则没有。（gcc还有一个与此无关的扩展，称为“向量”，与C++的“std::vector”无关。） - Keith Thompson

我指的当然是数组。如果我表达不清楚，对不起。 - userjuicer

Answer 1

我认为更有效的方法是最好的方法。例如:

• 分配一个向量，包括从0到N-1的所有索引，并对其进行初始化
• 通过使用其中一种高效排序算法(例如快速排序或归并排序)对索引向量进行排序，但是要参考原始数据向量(你排序的是索引，比较的是原始数据)

- Jack

---

好的回答。只是补充一些额外的信息：这种方法的时间复杂度为O(n*log(n))，由于受到排序操作的限制，它无法更好。 - Filipe Gonçalves

@FilipeGonçalves - 你是如何确定这种效率评级的？（即 _O(n*log(n)_）。你有链接吗？ - ryyker

@ryyker 好的，既然快速排序和归并排序都是O(n*log(n))的复杂度，那整个算法的复杂度也是如此。 - Filipe Gonçalves

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

- Rémi

---

你能否详细说明一下？因为当我在示例代码上测试时，它没有起作用。 - userjuicer

谢谢，现在我明白了。有例子总是很有帮助的。 - userjuicer

在 qsort 比较函数中使用减法，例如 return ( *(int*)a - *(int*)b );，会存在溢出的风险（考虑如果 a 是一个很大的负数而 b 是一个很大的正数）。 - Keith Thompson

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

- CapelliC