稳定化标准库中的qsort函数？

Question

稳定化标准库中的qsort函数？

25

我假设stdlib中的经典qsort函数不是稳定的，因为man页面没有提到它。这就是我所说的函数:

   #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;
    }
}

- twk

1

我不明白为什么你要比较指针。还有，你所说的“稳定”是什么意思（请原谅我的无知）。也许你可以在你的问题中详细说明一下。 - jmatthias

5

他所指的“稳定”是指如果项a与项b比较相等，并且a最初在数组中出现在b之前，那么在排序后，a仍将出现在b之前。这是排序领域中的术语，也是比较地址的技巧的原因。非常简洁明了。 - dmckee --- ex-moderator kitten

3

非常不错的想法，@dmckee，但不幸的是由于twk使用的是当前地址而不是起始地址，所以不稳定 :-) - paxdiablo

@paxdiablo：它不仅不稳定，而且通过违反比较函数的约束条件来调用未定义的行为。特别是，当对数组进行置换时，它可能导致某些qsort实现进入无限循环甚至执行越界写操作。 - R.. GitHub STOP HELPING ICE

老实说，只需使用一个外部、稳定的排序函数 :) - Mahmoud Al-Qudsi

你可以通过重新定义比较来实现这一点。将您想要进行的比较左移足够数量的位数，然后加上起始索引，这将最终落在最低有效位中。 - mathreadler

3个回答

14

在IT技术中，解决这个问题的标准方法是创建（即分配内存并填充）一个指向原始数组元素的指针数组，并使用qsort 对该新数组进行排序。使用额外的间接级别并在它们所指向的内容相等时返回指针值来进行比较。这种方法有可能副作用就是您根本不需要修改原始数组。但是如果您想最终对原始数组进行排序，则必须重新排列它以匹配qsort 返回后指针数组的顺序。

- R.. GitHub STOP HELPING ICE

代码示例将非常有益。 - undefined

2

这不起作用是因为在排序过程中，顺序会改变，两个元素的输出将不一致。为了使传统的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);
}

- milaniez

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pax · Accepted Answer

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

B,1
B,2
A,3

非稳定排序可能会比较B,1和A,3并将它们交换位置，导致结果如下：

A,3
B,2
B,1

如果下一步是将B,2与B,1进行比较，由于它们的键相同，并且B,2的地址小于B,1，因此不会发生交换。为了得到稳定排序，您应该得到以下结果：

A,3
B,1
B,2

唯一的方法是附加指针的起始地址（而不是当前地址），并将其与其他关键字一起排序。这样，原始地址就成为排序键的较小部分，因此，无论这两个B行在排序过程中走到哪里，B,1最终都会排在B,2之前。