1169 整数奇偶排序
大约 2 分钟
1169 整数奇偶排序
【算法】 排序、分类排序
【C++】 sort、vector、cmp 比较函数
【难度】 入门
一、题目简述
给定 10 个整数的序列,按以下规则重新排序:
- 奇数在前,偶数在后
- 奇数按从大到小排序
- 偶数按从小到大排序
二、解题思路
2.1 分类 + 分类内排序
和「合影效果」(DC1170)类似,先分类再分别排序:
- 遍历输入,把奇数和偶数分别放入两个数组
- 奇数数组:降序排序(
sort+greater<int>()或自定义 cmp) - 偶数数组:升序排序(默认
sort) - 先输出所有奇数,再输出所有偶数
2.2 另一种做法:一条 cmp 搞定
可以写一个比较函数,直接在 sort 中处理分类逻辑:
bool cmp(int a, int b) {
if ((a % 2) != (b % 2))
return (a % 2) > (b % 2); // 奇数(1) > 偶数(0),奇数在前
if (a % 2 == 1) // 都是奇数
return a > b; // 降序
return a < b; // 都是偶数,升序
}推荐分类法(方法一),思路更清晰。
2.3 手动模拟
输入:
7 3 10 2 5 8 9 4 1 6分类:
- 奇数:
7, 3, 5, 9, 1→ 降序排序 →9, 7, 5, 3, 1 - 偶数:
10, 2, 8, 4, 6→ 升序排序 →2, 4, 6, 8, 10
输出:9 7 5 3 1 2 4 6 8 10
三、参考代码
3.1 分类法(推荐)
#include <bits/stdc++.h>
using namespace std;
int main() {
int odd[15], even[15];
int o_cnt = 0, e_cnt = 0;
for (int i = 0; i < 10; i++) {
int x;
cin >> x;
if (x % 2 == 1) {
odd[o_cnt++] = x;
} else {
even[e_cnt++] = x;
}
}
// 奇数降序
sort(odd, odd + o_cnt, greater<int>());
// 偶数升序
sort(even, even + e_cnt);
// 先输出奇数
for (int i = 0; i < o_cnt; i++) {
cout << odd[i] << " ";
}
// 再输出偶数
for (int i = 0; i < e_cnt; i++) {
cout << even[i] << " ";
}
cout << endl;
return 0;
}3.2 单 cmp 法(一行排序)
#include <bits/stdc++.h>
using namespace std;
bool cmp(int a, int b) {
if ((a % 2) != (b % 2))
return (a % 2) > (b % 2); // 奇数在前
if (a % 2 == 1)
return a > b; // 奇数降序
return a < b; // 偶数升序
}
int main() {
int a[15];
for (int i = 0; i < 10; i++) {
cin >> a[i];
}
sort(a, a + 10, cmp);
for (int i = 0; i < 10; i++) {
cout << a[i] << " ";
}
cout << endl;
return 0;
}四、复杂度分析
- 时间复杂度:,,可以忽略不计。
- 空间复杂度:,存储输入和分类数组。
五、知识扩展
5.1 判断奇偶
if (x % 2 == 1) // 奇数
if (x % 2 == 0) // 偶数也可以用位运算:
if (x & 1) // 奇数(末位为 1)
if (!(x & 1)) // 偶数(末位为 0)位运算 x & 1 比 x % 2 稍快,但 % 2 编译器通常会自动优化,两者性能差异可忽略。
5.2 负数取模的注意事项
如果题目可能出现负数,x % 2 == 1 对负数无效(如 -3 % 2 = -1)。应该用:
if (x % 2 != 0) // 奇数(包含负奇数)或:
if ((x & 1) != 0) // 位运算不受符号影响本题输入全为正整数,用 x % 2 == 1 没问题。
