稳定标准库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

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

BBBB,1
BBBB,2
AAAA,3

Quicksort可以比较BBBB,1与AAAA,3并交换它们,给出:

AAAA,3
BBBB,2
BBBB,1

如果下一步是将BBBB,2与BBBB,1进行比较,则密钥将是相同的,并且由于BBBB,2的地址小于BBBB,1,因此不会进行交换.对于稳定的排序,您应该最终得到:

AAAA,3
BBBB,1
BBBB,2

唯一的方法是附加指针的起始地址(不是它的当前地址),并使用它以及其他键进行排序.这样,原始地址成为排序键的次​​要部分,因此无论两行在排序过程中的位置如何,BBBB,1最终都会结束.BBBB,2BBBB

Answer 2

规范的解决方案是为原始数组的元素指定数组(即分配内存和填充),以及qsort这个新数组,使用额外的间接级别,并在它们指向的东西时回退到比较指针值是平等的.这种方法有潜在的附带好处,你根本不修改原始数组 - 但是如果你想在最后对原始数组进行排序,你必须置换它以匹配指针数组中的顺序.qsort回报.