如何在c++中偶数和奇数递增之间交替排序?

Question

我有一个相等的偶数和奇数的数组。我想对数组进行排序，使其符合以下模式:even1, odd1, even2, odd2, even3, odd3，…依次类推，其中even1 <= even2 <= even3, odd1 <= odd2 <= odd3。

例如，如果数组是[1,2,3,4,5,6]。排序后的数组为[2,1,4,3,6,5]。

我想用std::sort比较函数来做。但不幸的是，我不能。我认为那是不可能的。

bool cmp(int lhs, int rhs) {
// couldn't write anything
}

Answer 1

首先，我认为这个问题需要改进，因为它非常不清楚。

不过，我会试着推测一下。

我有一个相等的奇偶整数数组。

基于此，由于偶数和奇数不能相等，我假设你想说你有相同数量的偶数和奇数，例如3个奇数和3个偶数，如输入[1, 2, 3, 4, 5, 6]的情况。

另一方面，我认为示例[1, 2, 3, 4, 5, 6]不够通用，因为一个奇偶校验的每个整数已经在另一个奇偶校验的两个连续整数之间，因此解决方案是交换前两个元素，然后是第二个两个元素，然后是第三个两个元素，以此类推。

一个更一般的例子是[1, 2, 5, 3, 10, 8]，它应该变成[2, 1, 8, 3, 10, 5]。

要得到它，一个策略是

1. 对vector/list/whatever进行分区，使得所有偶数占据其左侧，所有奇数占据其右侧([2,10,8,1,5,3])，
2. 对两个分区独立排序([2,8,10,1,3,5])，
3. 将它们压缩到范围-of-2 ([[2,1],[8,3],[10,5]])
4. 连接这些范围([2,1,8,3,10,5])

你可以很容易地在Range-v3中做到这一点，它看起来就像上面的列表:

#include <iostream>
#include <range/v3/action/sort.hpp>
#include <range/v3/algorithm/partition.hpp>
#include <range/v3/view/concat.hpp>
#include <range/v3/view/drop.hpp>
#include <range/v3/view/join.hpp>
#include <range/v3/view/single.hpp>
#include <range/v3/view/take.hpp>
#include <range/v3/view/zip_with.hpp>
#include <vector>
using ranges::partition;
using namespace ranges::actions;
using namespace ranges::views;
int main(){
std::vector<int> v{1, 2, 5, 3, 10, 8};
constexpr auto is_even = [](int i){ return i % 2 == 0; };

constexpr auto make_range_of_2 = [](int x, int y){
return concat(single(x), single(y));
};
partition(v, is_even); // partition
auto r = zip_with(make_range_of_2,
sort(v | take(v.size()/2)/* even integers */),
sort(v | drop(v.size()/2)/* odd  integers */))
| join/* range-or-ranges -> range */;
for (auto i : r) {
std::cout << i << std::endl;
}
}

考虑到一半的代码是#includes和usings，解决方案非常简洁。

让我们再看一遍，对比英语:

• 我们partition集合v使得所有的偶数在所有的奇数之前，

  partition(v, is_even);
  

• 我们zip_with功能make_range_of_2…

  auto r = zip_with(make_range_of_2,
  

• …v的前半部分(偶数)的sorted范围…

  sort(v | take(v.size()/2)),
  

• …v的后半部分(奇数)的sort的ed值，

  sort(v | drop(v.size()/2)))
  

• 最后我们把所有的"成对"组合在一起。我们用zip_with在一个大范围内得到的

  | join;
  

它解释了自己!

也许不太清楚的部分是make_range_of_2的实现。我们需要的是一个给定两个ints的函数，它返回一个只包含这两个CC_23 s的范围。我不知道是否有更简单的方法，但我能想到的第一个方法是通过single从每个int中创建一个1元素范围，然后concat创建它们。

Answer 2

正如在评论中提到的，不可能让您的Comparator完成所有需要的工作。因此，我们只需要一个自由函数来完成所需的工作。

#include <algorithm>
#include <iostream>
#include <vector>
std::vector<int> organize_numbers(const std::vector<int>& v) {
std::vector<int> evens;
std::vector<int> odds;
// Separate evens and odds
for (auto i : v) {
i & 1 ? odds.push_back(i) : evens.push_back(i);
}
std::sort(evens.begin(), evens.end());
std::sort(odds.begin(), odds.end());
// Zip evens and odds back together
std::vector<int> result;
std::size_t i = 0;
for (; i < evens.size() && i < odds.size(); ++i) {
result.push_back(evens[i]);
result.push_back(odds[i]);
}
// One of evens or odds may be longer
auto& remainder = evens.size() > odds.size() ? evens : odds;
for (; i < remainder.size(); ++i) {
result.push_back(remainder[i]);
}
return result;
}
int main() {
std::vector<int> nums{1, 2, 3, 4, 5, 6, 7, 9, 11, 13};
nums = organize_numbers(nums);
for (auto i : nums) {
std::cout << i << ' ';
}
std::cout << 'n';
}

函数将奇数和偶数分开，对奇数和偶数进行排序，并将它们压缩回一起。需要注意的是最后一个循环，用于处理偶数或奇数中的一个比另一个长的场景。Move语义使得值交换更便宜。

我确信有一种方法涉及std::partition来节省一点存储成本。您可以将偶数和奇数分开，分别对每个范围排序，然后交换值。这将允许您就地修改向量，这可能是需要的。

Answer 3

如果您创建一个compare函数，将所有奇数放在偶数之前，并在这些组中进行简单的比较，您可以在一个排序中将所有奇数排序，然后是所有偶数排序。

你需要正确地交换它们。

像这样

bool cmp(int lhs, int rhs) {
if ((lhs ^ rhs) & 1) // different oddness
return lhs & 1;  // place odds first
return lhs < rhs;
}