为什么 qsort 会为相同的数组但不同的排序产生不同的输出？

Question

我想借助 C 中的 qsort 对数组进行降序排序。

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

int compareFloat(const void* p1, const void* p2){
    const float* pa = p1;
    const float* pb = p2;
    return pb - pa;
}

int main()
{
    float arr[] = {1.5, 1.6, 1.38};
    qsort(arr, 3, sizeof(float), compareFloat);
    printf("%.2f %.2f %.2f", arr[0], arr[1], arr[2]);
    return 0;
}

以上代码输出为“1.60 1.38 1.50”，这是错误的；但是，当数组初始化为 float arr[] = {1.38, 1.6, 1.5} 时，答案是正确的（即“1.6, 1.5, 1.38”）。

为什么？

Answer 1

比较函数中

int compareFloat(const void* p1, const void* p2){
    const float* pa = p1;
    const float* pb = p2;
    return pb - pa;
}

您返回的是两个指针的差异。但是你需要比较指向的值而不是指针本身。

函数可以如下所示

int compareFloat( const void* p1, const void* p2)
{
    float a = *( const float * )p1;
    float b = *( const float * )p2;

    return ( a < b ) - ( b < a );
}

这是一个演示程序。

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

int compareFloat( const void *p1, const void *p2 )
{
    float a = *( const float * )p1;
    float b = *( const float * )p2;

    return ( a < b ) - ( b < a );
}

int main( void )
{
    float arr[] = { 1.5, 1.6, 1.38 };
    const size_t N = sizeof( arr ) / sizeof( *arr );

    qsort( arr, N, sizeof( float ), compareFloat );

    printf( "%.2f %.2f %.2f\n", arr[0], arr[1], arr[2] );
}

程序输出为

1.60 1.50 1.38

Answer 2

你的比较例程不正确。

return pb - pa;

此处您要减去两个指针值。

如果您使用的是整数，您应该减去指针指向的数字：

return *pb - *pa;

但是由于小数部分被截断，这不适用于浮点数。您需要明确比较 return 正确的值。

if (*pa > *pb) {
    return -1;
} else if (*pa < *pb) {
    return 1;
} else {
    return 0;
}

Answer 3

你的 compareFloat 函数的 return 值是错误的...... 两个原因。

首先，您要减去指针，而不是它们指向的值——因此您需要 *pb - *pa.

但是，即便如此，对于 1.6 和 1.5 这样的值，您的测试也会失败，因为该减法的结果将是 non-zero 但小于一个。因此，当转换为 int return 类型时，函数将 return 0 （表示值相同），即使它们不是。

您需要 return 至少两次比较的结果：

int compareFloat(const void* p1, const void* p2)
{
    const float* pa = p1;
    const float* pb = p2;
    return (*pa < *pb) - (*pa > *pb);
}

Answer 4

其他人很好地指出了2个不足：

OP的指针减法应该是浮点型FPsubtraction/compare.

结果必须是 int.

int compareFloat(const void* p1, const void* p2){
  const float* pa = p1;
  const float* pb = p2;
  // return pb - pa;
  return (*pb > *pa) - (*pb < *pa);
}

还有另一个问题：如果任一 FP 值可能是 not-a-number NAN，则需要额外关注以保持比较兼容。我们需要一种排序，当参数颠倒时，returns 符号相反。此外，如果 a > b 和 b > c，则 a > c。 (*pb > *pa) - (*pb < *pa) 上述内容无法通过 NAN 实现。

int compareFloat(const void* p1, const void* p2){
  const float f1 = *(const float *)p1;
  const float f2 = *(const float *)p2;
  if (isnan(f1)) {
    if (isnan(f2)) {
      // Since both are NA, just compare bit patterns
      return memcmp(p1, p2, sizeof (float));
    }
    return 1; // Consider NAN < all non-NANs
  }
  if (isnan(f2)) {
    return -1;
  }
  return (f2 > f1) - (f2 < f1);
}

int main() {
  float arr[] = {1.5f, 1.6f, NAN, 1.38f};  // Better to use float constants
  qsort(arr, 4, sizeof(float), compareFloat);
  printf("%.2f %.2f %.2f %.2f", arr[0], arr[1], arr[2], arr[3]);
  return 0;
}

输出

1.60 1.50 1.38 nan

为什么 qsort 会为相同的数组但不同的排序产生不同的输出？

Why does qsort produce different output for same array but different ordering?

c

sorting

comparison

qsort

function-definition