c++ - 给定条件如何维持发生顺序

Question

我偶然发现了这个 GeeksForGeeks，上面写着:使用内置排序函数重新排列正数和负数，使所有负整数出现在所有正整数之前，并且应保持出现顺序。

修改了 sort() 的比较函数以实现此目的。

bool comp(int a, int b)
{
    // This is to maintain order
    if ((a >= 0 && b >= 0) || (a < 0 && b < 0))
        return false;

    // Swapping is must
    if ((a >= 0) && (b < 0))
        return false;
    return true;
}

但是为什么顺序是由这个 block 维护的:

if ((a >= 0 && b >= 0) || (a < 0 && b < 0))
    return false;

Answer 1

这似乎是原始文章

https://www.geeksforgeeks.org/rearrange-positive-negative-numbers-using-inbuilt-sort-function/

它(某种程度上)是如何工作的:std::sort 根据比较器重新排列所有内容。该比较器基于“所有负数彼此完全相等。所有正数彼此完全相等。负数小于正数。”

如果您根据这些规则排序，您将得到所有负数，然后是所有正数。比较器本身不会打乱它们的顺序，除了看它们是大于还是小于零。 (而且数据集很方便地没有任何零。)

出了什么问题:

1) 比较函数没有正确处理 0。它给出了错误的答案，更糟糕的是，它给出了违反严格弱排序的答案。 (见下文)

2) std::sort 不是一个稳定的排序。不能保证保持秩序。他们在一组数据上很幸运。如果他们使用了 std::stable_sort 和一个正确的比较函数，那将是一个满足要求的“内置函数”。但是单靠比较函数并不能使算法稳定。参见 What is the difference between std::sort and std::stable_sort?或者只查看 http://www.cplusplus.com/reference/algorithm/sort/ 上的文档顶部附近

3) 他们用花哨的技巧想出一个复杂度为 O(n log n) 的解决方案，来解决一个非常简单的 O(n) 问题。因此，除了在多个点上都错了之外，它毫无理由地低效。

也许他们应该考虑 https://en.cppreference.com/w/cpp/algorithm/stable_partition如果允许我们只排除数据中的零。

---

这是严格弱排序的定义(也由一些程序员老兄链接) https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings

For all x in S, it is not the case that x < x (irreflexivity).
For all x, y in S, if x < y then it is not the case that y < x (asymmetry).
For all x, y, z in S, if x < y and y < z then x < z (transitivity).
For all x, y, z in S, if x is incomparable with y (neither x < y nor y < x hold), and y is incomparable with z, then x is incomparable with z (transitivity of incomparability).

请注意 comp(0, anything) 返回 false，因此 1 < 0 很容易破坏传递性，而且显然是错误的。