c - 稳定标准库qsort？

我假设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;
    }
}

最佳答案

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

BBBB,1
BBBB,2
AAAA,3

quicksort可以将bbbb，1与aaaa，3进行比较并交换它们，给出：

AAAA,3
BBBB,2
BBBB,1

如果下一步是将bbbb，2与bbbb，1进行比较，则密钥将相同，并且，由于bbbb，2的地址小于bbbbbb，1，则不会进行交换。对于稳定类型，您应该得到：

AAAA,3
BBBB,1
BBBB,2

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

关于c - 稳定标准库qsort？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/584683/