为什么我的比较器功能不起作用？

Question

我有一个元素为 的数组[0, 1, 0, 3, 12]。我想将所有零移到它的末尾，同时保持非零元素的相对顺序。移动后的数组应该如下所示[1, 3, 12, 0, 0]。为此，我编写了以下代码：

#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;
    }
}

我编写这段代码时认为，只要false在非零元素之前放置零，i就可以交换元素，但此代码给出的输出是，即[12, 3, 1, 0, 0]它只是按降序对元素进行排序。谁能解释一下为什么我的比较器功能不起作用？我可以使用比较器功能来做到这一点吗？

Answer 1

您的比较函数不满足比较函数的要求。例如，如果cmp( a, b )返回true则应cmp( b, a )返回false。

不使用算法，而是std::sort使用算法std::stable partition，例如

    std::stable_partition( std::begin( arr ), std::end( arr ), 
        []( const auto &x ) { return x != 0; } );

另一方面，如果非零元素没有排序，例如

int arr[] = { 0, 3, 0, 12, 1 };

std::sort如果你想对它们进行排序，那么你可以编写以下方式的调用

std::sort( std::begin( arr ), std::end( arr ),
    []( const auto &a, const auto &b )
    {
        return a != 0 && b != 0 ? a < b : a != 0;
    } );

这是一个演示函数

#include <iostream>
#include <iterator>
#include <algorithm>

int main()
{
    int arr[] = { 0,3,0,12,1 };
    //std::stable_partition( std::begin( arr ), std::end( arr ), 
    //  []( const auto &x ) { return x != 0; } );

    std::sort( std::begin( arr ), std::end( arr ),
        []( const auto &a, const auto &b )
        {
            return a != 0 && b != 0 ? a < b : a != 0;
        } );

    for (int i : arr) {
        std::cout << i << ' ';
    }
    std::cout << '\n';
}

程序输出是

1 3 12 0 0

或者，如果您愿意，您可以编写一个单独的比较 functopm 来代替 lambda 表达式

bool cmp( int a, int b )
{
    return a != 0 && b != 0 ? a < b : a != 0;
}

在这种情况下，调用std::sort将类似于

std::sort( std::begin( arr ), std::end( arr ), cmp );