20

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

3 回答 3

32

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

BBBB,1
BBBB,2
AAAA,3

快速排序可以将 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

于 2009-02-25T04:16:31.710 回答
10

规范的解决方案是制作（即分配内存并填充）一个指向原始数组元素的指针数组，以及qsort这个新数组，使用额外的间接级别并在指针指向的东西时回退到比较指针值是平等的。这种方法有一个潜在的好处是您根本不修改原始数组 - 但如果您希望原始数组最终排序，则必须对其进行置换以匹配指针数组中的顺序qsort返回。

于 2011-05-24T04:08:47.907 回答
0

这不起作用，因为在排序过程中，排序会发生变化，两个元素的输出将不一致。为了使老式的 qsort 稳定，我所做的是在我的结构中添加初始索引并在将其传递给 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);
}
于 2017-06-22T01:42:15.563 回答