如何使用 qsort 保持排序不变

Question

直接来自 qsort 手册，它说：

If two members compare as equal, their order in the sorted array is undefined.

但是，我希望 qsort 在相等时保持顺序不变。也就是说，如果两个元素具有用于排序的相同值，则保留它们在原始数组中的排序。

我不确定如何使用 qsort 执行此操作。我宁愿不使用替代排序库/自己滚动。

谢谢

--

编辑：现在我知道了稳定和不稳定排序之间的区别，我意识到这是重复的。

Answer 1

这里 qsort 告诉你的是他的算法不允许它保证你得到两个 equals 成员的排序顺序。

您可以做的是实施/使用另一种算法，或强制它们按照原来的方式排序：

如果您的比较函数return相等，请查看它们最初的排序方式，然后以相同的方式对它们进行排序。

Answer 2

你实质上是在问如何在不稳定排序之上实现稳定排序。

您无能为力：您只能控制比较功能，因此您必须在这方面努力。

一种可能是将第二个键 ID 附加到数组中与该元素的原始索引相对应的每个元素。那么，如果两个元素比较相等，就return按照它们原来的索引对应的顺序

Answer 3

qsort代表“Quick Sort”，这是一种快速但不稳定的排序算法。假设您按升序排序。在这种情况下，如果不交换具有相同键的元素，则排序算法称为 stable。如果它可以交换具有相同键的元素，则它是不稳定。

您的问题有不同的解决方案；我会在这里推荐其中两个。

解决方案 1

您可能会在维基百科中找到一些关于 stability of sorting algorithms，包括一种在您实际需要稳定算法时使用不稳定算法的方法：您 扩展排序键 ：例如，如果您使用整数值进行排序。

假设您正在对一个整数数组进行排序。取而代之的是，您创建了一个包含两个元素的结构：第一个 (KEY) 是您的整数。第二个 (AUX_KEY) 是一个 unique 索引。在排序之前，您线性设置 AUX_KEY 以反映原始顺序。排序时，传递给 qsort 一个函数，该函数将使用 KEY 进行排序，但如果两个键相等，则会恢复使用 AUX_KEY。

解决方案 2

不要使用快速排序，而是使用像 merge sort, which you probably have in your programming environment (for example, here's the FreeBSD manpage for mergesort; the same may be available in other programming environments under the same name -- please check) or, if you don't need speed too much, use insertion sort 这样稳定的算法（您可以自己编写代码——它只需要几行伪代码）。插入排序的时间复杂度为二次方（时间与 n^2 成正比），而归并排序和快速排序的时间复杂度为 O(n log(n)).

Answer 4

正如 GNU libc manual 所解释的那样，

The only way to perform a stable sort with qsort is to first augment the objects with a monotonic counter of some kind.

因此，除非您可以修改您的比较函数以便区分您当前考虑 "equal" 的对象，否则您必须在排序前使用索引显式注释您的对象，并在排序时删除索引完毕。你可以使用像

这样的东西

struct indexed {
    void *obj;
    int index;
}

如何使用 qsort 保持排序不变

How to leave ordering unchanged on equality using qsort

c

sorting

qsort

stable-sort