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

Question

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

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.000 000

错误，因为-1 和-1.1 的顺序改变了。 我相信这是因为我的“比较”功能而发生的。

我该如何解决这个问题？

谢谢

Answer 1

要添加到 @AnT 的现有答案，您可以通过 SortChecker< 自动验证您的 qsort 回调/a>：

$ 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

并检查生成的代码转储。

Answer 2

你的比较功能坏了。例如，它表示 -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 3

通过将差值四舍五入到整数，您会失去精度。

编辑：

将比较函数修改为

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

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

明确返回 0 的情况将花费额外的浮点计算，并且它们很少相等。因此，如果输入数据中的冲突率很小，则可以省略相等性比较。