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

Question

我已经读过需要比较函数需要qsort()有3个结果:

• 否定结果如果 val1 < val2
• 0 如果 val1 == val2
• 如果是积极的结果 val1 > val2

据我所知,排序数组只需要一个返回true或false的谓词.以冒泡为例:

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()比较函数需要有3种可能的结果而不是2呢？

Answer 1

qsort可以使用布尔比较函数而不是三向比较来编写，但规范表明它需要三向比较函数，并且一些（不是全部）实现利用了三种可能的情况。如果您的比较函数不符合规范，则会导致未定义的行为。在这种情况下，未定义的行为可能包括无法正确排序或在非常罕见的极端情况下触发缓冲区溢出，直到航天飞机从轨道返回时您可能不会注意到。所以不要这样做。

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

Answer 2

根据@Matteo Italia的评论，比较次数存在效率问题， 在某些情况下（例如当值为整数时），您可以使用等式 asa == b和are equal 来减少比较次数。!(a < b) && !(b < a)

另外，在更一般的情况下（不是在注释中特别提到的 qsort 中），您需要它来保证排序函数的稳定性。在相等的情况下，如果排序想要稳定，它应该知道比较中的相等性。您可以在这里了解更多有关排序稳定性的信息。因此，稳定的排序方法需要返回三个值。