c++ - 仅通过修改比较使 qsort 稳定？

Question

可能重复：
稳定标准库 qsort？

是否可以仅通过修改我的 comp op 来使整数的 qsort 稳定？那是我的代码。我在大约 5-7 大小的非常小的数组上使用它。

static int compare( const void *a, const void *b )
{
    const int A(*(const int*)(a));
    const int B(*(const int*)(b));

    return B - A;
}

Answer 1

如果您使用 C++，则stable_sort函数是稳定的并且具有 O(nlogn) 性能。

否则，就地快速排序本质上是不稳定的（我相信如此）。然而，使用额外数组存储信息的简单变体是稳定的。

我已经使用了至少一个qsort()不稳定的版本，因为一旦我发现我的机器上的一个输入案例产生的结果qsort()和stable_sort()为我的机器上的输入案例产生的结果是不同的。

Answer 2

您不能仅通过更改比较运算符来采用诸如快速排序之类的不稳定排序算法并使其稳定。您必须从稳定的排序算法开始，然后比较无关紧要（只要它是 C++ 中的严格弱排序）。

Answer 3

如果您要排序的数组真的很小，那么您最好使用另一种排序算法。参见例如答案：小型数组（32 或 64 个元素以下）的快速稳定排序和对非常小的列表进行排序的快速算法实现。