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

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;
    }
    return 0;
}

我写这段代码时认为只要在非零元素之前放置零就返回 false 我可以交换元素但是这段代码给出的输出为 [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

或者如果你愿意，那么你可以编写一个单独的比较函数来代替 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 );

Answer 2

你传递给

std::sort

的比较器需要是一个strict weak order。特别是，对于相同的值，您需要

cmp(x, x) = false

，并且至多

cmp(x, y)

和

cmp(y, x)

之一为真（这对于

cmp(1, 2) == cmp(2, 1) == true

不正确）

您希望订单中的所有元素都相等，但 0 除外，它大于所有其他元素。这可以通过这样的功能来完成：

bool cmp(int a, int b) {
    if (a==0) {
        if (b==0) return false;  // equal
        return false;  // a is greater
    }
    if (b == 0) return true;  // `a < 0`? True, since 0 is the greatest element
    return false;  // All other elements are equivalent, not less than
}

// Simplified to
bool cmp(int a, int b) {
    return b == 0 && a != 0;
}

然后您想使用

std::stable_sort

来保留等效元素的顺序。

---

然而，排序并不是最好的方法。您可以简单地将所有非零元素向前移动，然后用 0 填充后面的空间：

void move_zeroes_to_back(int* begin, int* end) {
    int* nonzero_begin = begin;
    for (; begin != end; ++begin) {
        if (*begin != 0) *nonzero_begin++ = *begin;
        // else Don't move zero values forward
    }
    // Fill in the rest
    for (; nonzero_begin != end; ++nonzero_begin) {
        *nonzero_begin = 0;
    }
}

这个算法的第一部分是

std::remove

所做的：

void move_zeroes_to_back(int* begin, int* end) {
    int* nonzero_end = std::remove(begin, end, 0);  // Remove all zero values
    std::fill(nonzero_end, end, 0);  // Replace removed zero values at the end
}