C++如何使用std::sort实现奇偶元素交替升序排列？

结论 #

这个需求无法仅通过给std::sort编写无状态自定义比较函数实现。

原因 #

std::sort要求传入的比较函数必须基于两个输入元素的自身属性，定义符合严格弱序的比较规则，比较结果不能依赖元素之外的全局上下文。
你要求的排序规则里，两个元素的先后顺序不仅和自身的奇偶性、数值大小有关，还和整个数组中比当前元素小的偶数、奇数的总数量有关：
举个例子，单独给你两个整数1和4，你无法直接判断谁应该在前：

• 如果全局数组是[1,2,3,4]，排序结果是[2,1,4,3]，此时1要排在4前面
• 如果全局数组是[1,4,5,6]，排序结果是[4,1,6,5]，此时4要排在1前面
  仅通过两个元素自身属性完全无法得到正确的比较结果，自然也写不出符合要求的cmp函数。

可行实现方案 #

你可以用拆分排序后拼接的方式实现，逻辑简单性能也稳定：

1. 把原数组拆分为偶数、奇数两个独立数组
2. 分别对两个数组做升序排序
3. 按「偶数第k个、奇数第k个」的顺序交替拼接得到最终结果

C++代码示例 #

#include <vector>
#include <algorithm>

std::vector<int> specialSort(std::vector<int> origin) {
    std::vector<int> evens, odds;
    // 拆分奇偶
    for (int num : origin) {
        num % 2 == 0 ? evens.push_back(num) : odds.push_back(num);
    }
    // 分别排序
    std::sort(evens.begin(), evens.end());
    std::sort(odds.begin(), odds.end());
    // 交替拼接
    std::vector<int> res;
    for (int i = 0; i < evens.size(); ++i) {
        res.push_back(evens[i]);
        res.push_back(odds[i]);
    }
    return res;
}

如果你一定要用std::sort完成，需要先预处理给每个元素打上权重标签，再基于权重排序，本质还是和上面的逻辑一致：

• 第k小的偶数权重为2*k
• 第k小的奇数权重为2*k + 1
  按权重升序排序即可得到想要的结果，只是这个步骤需要先统计全局的奇偶排序信息，无法仅靠cmp函数完成。

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