为何自定义Comparator函数失效？能否用其实现数组零元素后置？

我拥有一个元素为[0, 1, 0, 3, 12]的数组，希望将所有零元素移至数组末尾，同时保持非零元素的相对顺序，处理后的数组应为[1, 3, 12, 0, 0]。为此我编写了以下C++代码：

#include <bits/stdc++.h>

using namespace std;

bool cmp(int a, int b){
    if (a == 0) {
        return a > b;
    } else {
        return true;
    }
}

int main(){
    int arr[] = {0, 1, 0, 3, 12};
    sort(arr, arr + 5, cmp);
    for (int i: arr) {
        cout << i;
    }
}

运行后输出为[12, 3, 1, 0, 0]（元素按降序排列），请问我的Comparator函数为何失效？能否用该函数实现需求？

一、为什么你的Comparator函数失效？ #

C++的sort要求自定义比较函数必须符合严格弱序规则，你的cmp直接违反了这个规则，导致排序逻辑彻底混乱：

• 当两个参数都是非零元素时，不管谁在前谁在后，cmp(a,b)和cmp(b,a)都会返回true。但严格弱序要求：如果a应该排在b前面，那b绝对不能排在a前面，你的写法完全打破了这个逻辑。
• 另外你对比较函数的逻辑理解也有误：cmp(a,b)返回true的意思是「a应该放在b的前面」。你给所有非零元素互比时返回true，等于告诉sort「任何非零元素都要排在另一个非零元素前面」，这显然会让sort把非零元素乱序排列，最终出现降序的结果。

二、能不能用Comparator实现需求？ #

可以，但得写对符合规则的比较函数，而且必须用stable_sort而不是sort——因为sort是不稳定排序，哪怕比较函数写对了，也保不住非零元素的原始顺序。

正确的比较逻辑应该是：

• 非零元素必须排在零元素前面；
• 两个非零元素之间，我们认为它们「不需要交换顺序」，这样stable_sort就会保留它们的原始相对位置。

修改后的代码如下：

#include <bits/stdc++.h>

using namespace std;

bool cmp(int a, int b){
    // 非零在前，零在后
    if (a != 0 && b == 0) return true;
    if (a == 0 && b != 0) return false;
    // 两个都是非零或都是零，返回false表示不交换
    return false;
}

int main(){
    int arr[] = {0, 1, 0, 3, 12};
    // 用stable_sort保证非零元素的原始顺序
    stable_sort(arr, arr + 5, cmp);
    for (int i: arr) {
        cout << i << " ";
    }
}

不过说实话，用排序来做移零有点杀鸡用牛刀，双指针法才是更高效的方案，时间复杂度O(n)，比排序的O(n log n)快得多：

#include <bits/stdc++.h>

using namespace std;

int main(){
    int arr[] = {0, 1, 0, 3, 12};
    int n = 5;
    int idx = 0;
    // 把所有非零元素移到数组前面
    for (int i = 0; i < n; ++i) {
        if (arr[i] != 0) {
            arr[idx++] = arr[i];
        }
    }
    // 剩下的位置全部补零
    while (idx < n) {
        arr[idx++] = 0;
    }
    for (int i: arr) {
        cout << i << " ";
    }
}

内容的提问来源于stack exchange，提问作者manofculture