c - 稳定标准库 qsort？

Question

我假设 stdlib 中的旧 qsort 函数不稳定，因为手册页没有说明任何相关内容。这是我正在谈论的功能:

   #include <stdlib.h>
   void qsort(void *base, size_t nmemb, size_t size,
              int(*compar)(const void *, const void *));  

我假设如果我更改我的比较函数以也包括我正在比较的地址，它将是稳定的。那是对的吗？

例如:

int compareFoos( const void* pA, const void *pB ) {
    Foo *pFooA = (Foo*) pA;
    Foo *pFooB = (Foo*) pB;

    if( pFooA->id < pFooB->id ) {
        return -1;
    } else if( pFooA->id > pFooB->id ) {
        return 1;
    } else if( pA < pB ) {
        return -1;            
    } else if( pB > pA ) {
       return 1;
    } else {
       return 0;
    }
}   

Answer 1

不，不幸的是你不能依赖它。假设您有数组(每条记录中有两个字段用于检查，但只有第一个字段用于排序):

B,1
B,2
A,3

不稳定排序可能会将 B,1 与 A,3 进行比较并交换它们，给出:

A,3
B,2
B,1

如果下一步是将 B,2 与 B,1 进行比较，则 key 将相同，因为 B,2 > 的地址小于 B,1，不会发生交换。对于稳定排序，您应该以:

A,3
B,1
B,2

唯一的方法是附加指针的起始地址(不是它的当前地址)并使用该地址和其他键进行排序。这样，原始地址成为排序键的次​​要部分，这样 B,1 最终将在 B,2 之前结束，而不管两个 B 在哪里 行在排序过程中。