P4675 整数奇偶排序（基础）

解题思路

第一步，分盒子装数。 准备两个盒子：odd 装奇数、even 装偶数。依次读入 10 个数，每读一个判断一次：除以 2 余 1 就是奇数，放进 odd；否则（余 0，包括 0 本身）放进 even。注意：0 是偶数，要放进偶数盒子，千万别放错。

第二步，分别排序。 奇数盒子里的数要按从大到小排，sort 默认是升序，所以要写一个比较函数 cmp，返回 x > y 实现降序；偶数盒子按从小到大排，sort 默认就是升序，直接用即可。

第三步，按顺序输出。 先输出奇数盒子里的全部数，再输出偶数盒子里的全部数，相邻两个数之间用空格隔开。用一个 first 标记控制在数前面加空格：第一个数前不加，后面的数前都加一个空格，避免末尾多一个空格。

想一想生活里的例子。 老师让男生一队、女生一队，男生队按身高从高到矮站，女生队按身高从矮到高站，两队前后排好。

用例子验证。 输入 10 个数 1 2 3 4 5 6 7 8 9 0：奇数盒子得到 9 7 5 3 1（从大到小），偶数盒子得到 0 2 4 6 8（从小到大）。先输出奇数再输出偶数：9 7 5 3 1 0 2 4 6 8，和题目要求完全一致。

边界情况： 固定只有 10 个数，两个数组各开 20 足够；输出顺序是"奇数在前、偶数在后"，千万不要搞反。

参考代码

// P4675 整数奇偶排序：奇数在前从大到小，偶数在后从小到大
#include <iostream>
#include <algorithm>
using namespace std;

int odd[20], even[20];

bool cmp(int x, int y) {
    return x > y; // 降序
}

int main() {
    int oddCnt = 0, evenCnt = 0, num;
    for (int i = 0; i < 10; i++) {
        cin >> num;
        if (num % 2 == 1) odd[oddCnt++] = num; // 奇数
        else even[evenCnt++] = num;            // 偶数（0也属于偶数）
    }
    sort(odd, odd + oddCnt, cmp); // 奇数从大到小
    sort(even, even + evenCnt);    // 偶数从小到大
    bool first = true;
    for (int i = 0; i < oddCnt; i++) {
        if (!first) cout << ' ';
        cout << odd[i];
        first = false;
    }
    for (int i = 0; i < evenCnt; i++) {
        if (!first) cout << ' ';
        cout << even[i];
        first = false;
    }
    cout << endl;
    return 0;
}

复杂度分析

固定只有 10 个数，sort 排序 10 个数的时间 O(10 log 10)，可以看成常数时间。空间复杂度 O(10)，两个小数组各放几个数。