使用自定义比较器时如何在 C++ 中执行稳定排序？

Question

我正在尝试用 C++ 编写自定义比较器来对向量进行排序。为了简单起见，我会说我的排序标准是所有偶数值都应该在所有奇数值之前，我正在尝试为此编写一个自定义比较器。但是我需要确保保留所有偶数元素和所有奇数元素的相对顺序。

我正在使用此代码：

bool mysort(int arg1,int arg2){
    return arg1%2==0;
}

int main(){
    vector<int> v({1,3,2,4,5,7,9,6,8,11,10,12});
    stable_sort(v.begin(),v.end(),mysort);
    for(int i=0;i<v.size();i++){
        cout<<v[i]<<" ";
    }
    return 0;
}

根据我的理解，当 mysort() returns 为真时，这意味着允许第一个参数 (arg1) 在第二个参数 (arg2) 之前。这就是为什么我在比较器中使用 return arg1%2==0; 的原因。

但是我得到的输出是12 10 8 6 4 2 1 3 5 7 9 11。这意味着，偶数元素的相对顺序是相反的。同时，保留奇数元素的相对顺序。

相反，如果我在 mysort() 比较器中使用 return i%2==0 && j%2!=0;，我得到的输出是 2 4 6 8 10 12 1 3 5 7 9 11。这保留了所有奇数和偶数元素的相对顺序。

为什么会出现这种行为？在保留相似元素的相对顺序的情况下编写自定义比较器的最佳方法是什么？提前谢谢你。

Answer 1

我相信您知道，stable_sort 保留比较相等的元素的顺序。为此，当 i 和 j 比较相等时，mysort (i, j) 和 mysort (j, i) 必须 return false。（当然 i < j 时也必须 return true。）

因此，您必须在 mysort 中测试 arg1 % 2 和 arg2 % 2 才能履行此合同，而 return arg1 % 2 == 0 && arg2 % 2 != 0; 正是您想要的：它将 return false 当 arg1 % 2 和 arg2 % 2 比较相等时，无论参数传递给它的顺序如何。

Answer 2

STL 使用小于比较，这意味着 std::stable_sort() 将以相反的顺序传递参数，它将调用 mysort(later_object，较早的对象)，因此 [=如果 later_object < earlier_object（将 later_object 复制到合并输出），则 20=] 值为真，如果 later_object >= earlier_object（复制 [=15]，则值为假=]合并输出）。

Answer 3

sort 和 stable_sort 的比较器必须引入 严格的弱顺序 。您的比较器不满足此条件。

严格弱顺序的属性之一是对于i和j的任何允许值，最多[=15]之一=] 和 mysort(j,i) 可以 return true。对于这两种情况，例如 i=2 和 j=4.

，您的比较器 returns true

要解决这个问题，您必须修改比较器。 arg1 什么时候比 arg2“少”？只有一种情况：当arg1为偶数且arg2为奇数时。因此，可用的定义是：

bool mysort(int arg1,int arg2){
    return arg1 % 2 == 0 && arg2 % 2 != 0;
}

顺便说一句，当你定义一个比较器时，你没有时间考虑算法将以什么顺序传递参数。所有（之前，之后）的讨论都是无关紧要的。该算法将按其喜欢的顺序传递参数。没有任何保证。

使用自定义比较器时如何在 C++ 中执行稳定排序？

How to perform stable sort in C++ when using a custom comparator?

c++

sorting

comparator

stable-sort

c++14