为什么传给qsort()的比较函数需要返回三个不同的值？

Question

我读到过，qsort()所需的比较函数需要有三种结果：

• 如果val1 < val2，则返回负数
• 如果val1 == val2，则返回0
• 如果val1 > val2，则返回正数

据我所知，仅需要一个返回真或假的谓词即可对数组进行排序。以冒泡排序为例：

int compare(int a, int b)
{
    if(a>b) return 1;
    return 0;
}
void bubbleSort(int arr[], int n) 
{
    int i, j;
    for (i = 0; i < n-1; i++)  
        for (j = 0; j < n-i-1; j++)  
            if ( compare(arr[j],arr[j+1]) ) 
                swap(&arr[j], &arr[j+1]);
}

那么为什么qsort()比较函数需要有三种可能的结果而不是两种呢？

- MihaiM

---

在我看来，这与将二分查找作为三分查找的坏习惯有关，而在相等情况下提前终止。在大多数情况下，这是适得其反的。 - user1196549

Answer 1

qsort 可以使用布尔比较函数代替三向比较，但是规范要求使用三向比较函数，并且一些（不是全部）实现利用了三种可能的情况。如果您的比较函数不符合规范，则会导致未定义行为。在这种情况下，未定义行为可能包括无法正确排序或触发非常罕见的角落案例上的缓冲区溢出，您可能直到航天飞机从轨道返回才会注意到。因此，请不要这样做。

至于为什么实现可能需要三向比较，这里有一个可能性：对于具有大量重复值的输入，快速排序可以通过使用三向分区来显著加快速度。这可以通过在相反方向上两次执行比较来使用双向比较完成，但是实现者知道需要三向比较器时，可能会在想要知道相等性时测试相等性。

- rici

Answer 2

如果元素 A == 元素 B，但比较函数告诉 qsort B > A，那么 qsort 将认为可能存在其他应该位于 A 和 B 之间的元素，而事实并非如此，因此会执行不必要的检查。

- Weather Vane

Answer 3

从技术上讲，你只需要使用小于号，因为a == b等同于!(a < b) && !(b < a)。

- user1196549

---

那就是，假设完全排序。因为我们正在排序，所以这似乎很明显，但重要的是要记住，在一般情况下等价性并不成立。 - spectras

a == b 相当于 !(a < b) && !(b < a)，但在浮点数运算中并不总是成立。 - chux - Reinstate Monica

@yves：如果a和b中至少有一个是NaN，则所有比较都返回false。但是!false && !false是true。 - rici

@yvesDaoust说：“布尔战争也是如此，但事实就是这样。”（对于我的清单而言，具有歧义的签名 char 是最前面的项 :-)） - rici

@YvesDaoust，比较返回NaN？这怎么可能？如果你执行了if (a < b)，而b恰好是NaN，程序仍然需要决定是否运行条件块…… - ilkkachu

Answer 4

如果快速排序的内部循环写成等价于这样：

while(x[i] < pivot) i++;  // less-than
while(pivot < x[j]) j--;  // less-than

然后你只需实现<即可。无论如何，遵循最小惊讶原则，使调用者更明显地知道应该做什么--如果你的比较函数指针命名为compare且该函数不应像常规stdlib qsort比较委托那样工作，则这是一个坏主意。另一方面，如果你的参数命名为less_than或isLessThan之类的名称，那么对于调用者来说，期望从比较函数中得到什么将更加明显：

 void sort(
     const void * arr,
     size_t num_items,
     size_t element_size, 
     bool (*is_less_than)(const void*, const void*)
 );

- vgru

Answer 5

根据@Matteo Italia的评论，比较次数存在效率问题，您可以使用等式a == b和!(a < b) && !(b < a)在某些情况下（例如当值为整数时）减少比较次数。此外，在更一般的情况下（不仅限于qsort），需要确保排序函数的稳定性。在相等的情况下，如果排序要保持稳定，它应该知道比较中的相等性。您可以在这里了解有关排序稳定性的更多信息。因此，对于稳定排序方法，需要返回三个值。

- OmG

---

@MatteoItalia 当 a,b 是浮点数且一个值可能是非数字时，(a == b <-> !(a < b) && !(b < a)) 不一定成立。 - chux - Reinstate Monica

qsort() 没有被指定为稳定的。 - chux - Reinstate Monica

更一般地说，我之前评论中的 < 和 == 并不是指 C 运算符 - 甚至仅对于字符串也没有意义 - 而是指由给定排序关系引起的比较运算符，即严格弱序。 - Matteo Italia

一个三向排序对于稳定排序而言几乎是必需的。虽然从技术上讲是正确的，但对于讨论为什么需要使用qsort()并不是非常相关。 - chux - Reinstate Monica

真实的，三元排序要求的相关性是OP探索的一个好点 - 就像FP数学的(a == b <-> !(a < b) && !(b < a))问题一样，探索排序也是个好点。 - chux - Reinstate Monica