我需要找到一个整数数组中元素的降序排列。
例如:
如果我有一个数组:
x = {24, 55, 22, 1}
我希望您能提供一份用C语言编写的算法,其结果为数组
order
,其中:order = {2, 1, 3, 4}
考虑到我的数组 x
可能会变得非常大(从1k-1M),我的问题如下:如何以尽可能高效(快速)的方式获取 order
数组?显然,必须存在一种有效的算法来实现这一点,对吗?
我需要找到一个整数数组中元素的降序排列。
例如:
如果我有一个数组:
x = {24, 55, 22, 1}
order
,其中:order = {2, 1, 3, 4}
考虑到我的数组 x
可能会变得非常大(从1k-1M),我的问题如下:如何以尽可能高效(快速)的方式获取 order
数组?显然,必须存在一种有效的算法来实现这一点,对吗?
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);
}
qsort
比较函数中使用减法,例如 return ( *(int*)a - *(int*)b );
,会存在溢出的风险(考虑如果 a
是一个很大的负数而 b
是一个很大的正数)。 - Keith Thompson我会从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);
}