qsort中的比较函数如何工作？

Question

我在网上找到了这个示例代码，它解释了qsort函数的工作原理。但我无法理解比较函数返回什么。

#include "stdlib.h"

int values[] = { 88, 56, 100, 2, 25 };

int cmpfunc (const void * a, const void * b) //what is it returning?
{
   return ( *(int*)a - *(int*)b ); //What is a and b?
}


int main(int argc, _TCHAR* argv[])
{

   int n;

   printf("Before sorting the list is: \n");
   for( n = 0 ; n < 5; n++ ) {
      printf("%d ", values[n]);
   }

   qsort(values, 5, sizeof(int), cmpfunc);

   printf("\nAfter sorting the list is: \n");
   for( n = 0 ; n < 5; n++ ) {
      printf("%d ", values[n]);
   }
    return 0;
}

- user968000

---

它们是从数组 values 中读取的整数。该函数返回 a - b 的值，如果 a 较小，则为 < 0（负数），如果它们相等，则为 0，或者如果 a 较大，则为 > 0（正数）。 - Ken White

一个用于qsort的比较函数（实际上是回调函数）应该返回与strcmp()完全相同的值。也就是说，如果第一项小于第二项，则返回-1；如果两项匹配，则返回0；如果第一项大于第二项，则返回1。 - user3629249

@user3629249：要小心，不要测试特定的值“-1”或“1”：strcmp()（或传递给qsort()的比较函数）允许对这些情况返回任何负数或正数值。 - Michael Burr

这个比较函数很糟糕，永远不要使用它。假设你正在对-1500000000和1500000000进行排序。减法的结果是-3000000000，而这个数字无法在int中表示，因此行为未定义。更糟糕的是，生成的代码通常会将其包装成一个正数1294967296，这完全破坏了排序。查看AnT的答案以获取正确的函数，以及此问答集中关于如果使用此比较函数会发生什么的内容。 - Antti Haapala -- Слава Україні

Answer 1

a 和 b 在 qsort 的文档中有明确说明：它们是指向需要进行比较的数组元素的指针。

在这种情况下，比较函数知道数组元素的类型是 int。因此，它将 void * 指针转换为 int * 类型，并通过减去第二个值从而对指向的 int 值进行三态比较。

尽管它能够正确地处理您的值集，但一般情况下使用减法进行三态比较是不好的编程习惯，因为它容易溢出。另外，在您的示例代码中，该函数不必要地消除了指向值的 const 限定符。

更好的选择是：

int cmpfunc(const void *a, const void *b)
{
   const int *A = a, *B = b;
   return (*A > *B) - (*A < *B);
}

- AnT stands with Russia

Answer 2

int cmpfunc (const void * a, const void * b) //what is it returning?
{
   return ( *(int*)a - *(int*)b ); //What is a and b?
}

相当于：

int cmpfunc (const void * a, const void * b) //what is it returning?
{
   // qsort() passes in `void*` types because it can't know the actual types being sorted
   // convert those pointers to pointers to int and deref them to get the actual int values

   int val1 = *(int*)a;
   int val2 = *(int*)b;

   // qsort() expects the comparison function to return:
   // 
   //    a negative result if val1 < val2
   //    0 if val1 == val2
   //    a positive result if val1 > val2

   return ( val1 - val2 ); 
}

- Michael Burr

---

如果要比较符号不同的大数，这个比较函数会发生整数溢出。在生产代码中应该避免使用它（至少要避免）。请参见https://stackoverflow.com/questions/53821538/possible-bug-in-std-c-quicksort-am-i-missing-something，以了解某些人在尝试使用它时遇到的问题。 - rici

请参考 AnT 的答案（https://dev59.com/yIXca4cB1Zd3GeqPM74w#27284248）获取正确的翻译。 - Antti Haapala -- Слава Україні

Answer 3

每当排序算法需要找出哪个元素应该放在另一个元素之前时，它会调用比较函数并传递指向这两个元素的指针。由于你正在对 int 值进行排序，所以这些指针实际上是指向 int 的指针，但签名必须采用 void*，以便可以与任何数据类型一起使用。因此，为了获得实际的元素值，a 必须转换为 int*，然后被解除引用 - 因此，*(int*)a。如果 a 应该放在 b 之前，则函数必须返回负值；如果 b 应该放在 a 之前，则返回正值；如果无所谓哪个先放（即元素相等的情况），则返回零。在这种特殊情况下，由于我们正在处理数字，如果希望最大的数字先放，只需从 a 的值中减去 b 的值即可。请保留 HTML 标签。

- Aasmund Eldhuset

Answer 4

来自于http://en.cppreference.com/w/cpp/algorithm/qsort

cmp函数返回一个负整数，如果第一个参数小于第二个参数，返回一个正整数，如果第一个参数大于第二个参数，则返回零。

该函数使用void指针，因此qsort函数可用于任何数据类型。但是在cmp函数内部，您必须显式地将指针转换为实际的数据类型。

- vsoftco

Answer 5

a 和 b 被作为整数进行比较 - 它们必须作为 void * 传递，但最终在解除引用之前被强制转换为 int *。至于返回值，它将是正���、负数或零，所有这些都将在排序函数中考虑到。

- chris

Answer 6

qsort会将需要比较的每一对元素传递给cmpfunc，并使用其返回值来确定哪个更大，然后相应地对数组进行排序。

基本上，如果比较函数返回正数，则意味着第一个参数大于第二个参数。同样，如果它返回负数，则第二个参数更大。

在这个例子中，我们想要对整数进行排序。因此，在比较给定数组的两个元素时，我们需要决定哪个更大。为了比较它们，简单的减法运算就足够了，因为当a更大时结果是正数，当a和b相等时结果为0，当b更大时结果为负数。

- emre.