稳定标准库qsort？

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

#include  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 id ) { return -1; } else if( pFooA->id > pFooB->id ) { return 1; } else if( pA  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,2之前结束BBBB,2无论两个BBBB行在排序过程中的位置如何。

Answer 2

规范的解决方案是为原始数组的元素制作（即分配内存和填充）指针数组，并使用额外的间接级别对这个新数组进行qsort ，并在他们指向的东西时回退到比较指针值是平等的。 这种方法有潜在的副作用，你根本不修改原始数组 – 但如果你想让原始数组最后排序，你必须置换它以匹配指针数组中的顺序后qsort返回。

Answer 3

这不起作用，因为在排序过程中，排序将改变，两个元素将不具有一致的输出。 我做的好的老式qsort稳定是在我的struct中添加初始索引并在将它传递给qsort之前初始化该值。

 typedef struct __bundle { data_t some_data; int sort_score; size_t init_idx; } bundle_t; /* . . . . */ int bundle_cmp(void *ptr1, void *ptr2) { bundle_t *b1, *b2; b1 = (budnel_t *) ptr1; b2 = (budnel_t *) ptr2; if (b1->sort_score < b2->sort_score) { return -1; } if (b1->sort_score > b2->sort_score) { return 1; } if (b1->init_idx < b2->init_idx) { return -1; } if (b1->init_idx > b2->init_idx) { return 1; } return 0; } void sort_bundle_arr(bundle_t *b, size_t sz) { size_t i; for (i = 0; i < sz; i++) { b[i]->init_idx = i; } qsort(b, sz, sizeof(bundle_t), bundle_cmp); }