c++ - stable_sort 的自定义比较函数

Question

我想对 int32_t 数组进行排序，使得所有正数(包括零)首先出现，然后是所有负数。输出中 +ve 和 -ve 数字的相对顺序应与输入的相对顺序相同。例如。

Input  : 9, 4, -2, -1, 5, 0, -5, -3, 2 <br>
Expected Output : 9, 4, 5, 0, 2, -2, -1, -5, -3

但是，我得到以下输出:

Actual output : 2 0 5 4 9 -3 -5 -1 -2 <br>

输出部分准确，+ve 然后 -ve，但 +ve 和 -ve 数字的列表是相反的。有人可以帮忙吗？

#include <iostream>
#include <algorithm>
using namespace std;


bool comp(int32_t lhs, int32_t rhs)
{
    if ( (lhs < 0) && (rhs >= 0) )
        return false;
    else
        return true;
}


int main()
{
    vector<int32_t> input{9, 4, -2, -1, 5, 0, -5, -3, 2};

    // sort +ve, then -ve
    stable_sort(input.begin(), input.end(), comp);
    for (int32_t i : input)
        cout << i << " ";
    cout << endl;

    return 0;
}

谢谢你，艾哈迈德。

Answer 1

您的比较函数不满足严格弱排序的要求。具体来说，就是非自反性。也就是说，对于所有a，

comp(a, a) == false

例如，在您的函数中，comp(0, 0) 将返回 true。试试这个:

bool comp(int32_t lhs, int32_t rhs)
{
    if (lhs < 0)
        return false;
    return rhs < 0;
}

但实际上，您所描述的操作是一个分区。您更适合将 std::stable_partition 与检查值是否 >= 0 的谓词结合使用。

auto ge_0 = [](int A) { return A >= 0; };
std::stable_parition(input.begin(), input.end(), ge_0);