尝试使用C qsort函数时出现问题

#include  #include  float values[] = { 4, 1, 10, 9, 2, 5, -1, -9, -2,10000,-0.05,-3,-1.1 }; int compare (const void * a, const void * b) { return ( (int) (*(float*)a - *(float*)b) ); } int main () { int i; qsort (values, 13, sizeof(float), compare); for (i = 0; i < 13; i++) { printf ("%f ",values[ i ]); } putchar('\n'); return 0; } 

结果是：

-9.000000 -3.000000 -2.000000 -1.000000 -1.100000 -0.050000 1.000000 2.000000 4.000000 5.000000 9.000000 10.000000 10000.000000

这是错误的，因为-1和-1.1的顺序被改变了。 我相信它正在发生，因为我的“比较”function。

我怎样才能解决这个问题？

谢谢

Answer 1

您的比较function已损坏。 例如，它表示-1.0等于（等价） -1.1 ，因为(int) ((-1.0) - (-1.1))为零。 换句话说，你自己告诉qsort -1.0和-1.1的相对顺序无关紧要。 为什么你感到惊讶的是，在结果排序中这些值没有排序？

通常，您应该避免通过从一个减去另一个来比较数值。 它只是不起作用。 对于浮点类型，由于很多不同的原因，它可能会产生不精确的结果，其中一个原因是您自己观察到的。 对于整数类型，它可能会溢出。

用于比较qsort两个数值a和b的通用惯用法看起来像(a > b) - (a < b) 。 记住它并使用它。 在你的情况下将是

 int compare (const void * a, const void * b) { float fa = *(const float*) a; float fb = *(const float*) b; return (fa > fb) - (fa < fb); } 

在C代码中，定义宏可能非常有意义

 #define COMPARE(a, b) (((a) > (b)) - ((a) < (b))) 

并使用它而不是明确地拼写比较。

Answer 2

通过将差异舍入为整数，您将失去精度。

编辑：

将比较function修改为

return (*(float*)a >= *(float*)b) ? 1 : -1;

为AndreyT编辑：我不认为只返回1或-1将导致无限循环或不正确的排序（它只会交换不需要它的相等值）。

具有返回0的明确情况将花费额外的浮点数，并且它们很少相等。 因此，如果输入数据中的碰撞率很小，则可以省略对等式的比较。

Answer 3

要通过@AnT添加到现有答案，您可以通过SortChecker自动validation您的qsort回调：

 $ LD_PRELOAD=$HOME/sortcheck-master/bin/libsortcheck.so ./a.out a.out[7133]: qsort: comparison function is not transitive (comparison function 0x4005cd (/home/iuriig/a.out+0x4005cd), called from 0x400614 (/home/iuriig/a.out+0x400614), cmdline is "./a.out") -9.000000 -3.000000 -2.000000 -1.000000 -1.100000 -0.050000 1.000000 2.000000 4.000000 5.000000 9.000000 10.000000 10000.000000 

此警告表示，对于某些输入， compare报告x < y, y < z而不是x < z 。 要进一步调试此问题，请运行

 export SORTCHECK_OPTIONS=raise=1 

并检查生成的codedump。