C++计数排序实现奇偶数分类排序完整教程

我会为您提供 C++ 实现，使用**计数排序**来分别对奇数和偶数进行排序。 ## 📌 解题思路 - 因为输入的正整数范围未知，但计数排序适用于**值域有限**的情况。题目未明确范围，但我们可以采用**简化版计数排序**：分别用两个 `vector<int>` 存储奇数和偶数，然后使用**计数排序**（基于值域确定）。 - 由于 n ≤ 100，并且正整数范围通常不会太大，可以从输入中动态找出最小/最大值，再分配计数数组。 ## 💻 完整C++代码 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; // 计数排序：对容器中的元素进行排序（值域在[minVal, maxVal]） void countingSort(vector<int>& arr, int minVal, int maxVal) { int range = maxVal - minVal + 1; vector<int> count(range, 0); // 统计每个值出现的次数 for (int num : arr) { count[num - minVal]++; } // 重建排序后的数组 arr.clear(); for (int i = 0; i < range; i++) { while (count[i] > 0) { arr.push_back(minVal + i); count[i]--; } } } int main() { int n; cin >> n; vector<int> odds, evens; // 读取n个正整数并分类 for (int i = 0; i < n; i++) { int x; cin >> x; if (x % 2 == 1) { odds.push_back(x); } else { evens.push_back(x); } } // 分别对奇数和偶数进行计数排序 // 因为不知道具体范围，可以先找到各自的最小值最大值 if (!odds.empty()) { int minO = *min_element(odds.begin(), odds.end()); int maxO = *max_element(odds.begin(), odds.end()); countingSort(odds, minO, maxO); } if (!evens.empty()) { int minE = *min_element(evens.begin(), evens.end()); int maxE = *max_element(evens.begin(), evens.end()); countingSort(evens, minE, maxE); } // 输出奇数行 for (int i = 0; i < odds.size(); i++) { if (i > 0) cout << " "; cout << odds[i]; } cout << endl; // 输出偶数行 for (int i = 0; i < evens.size(); i++) { if (i > 0) cout << " "; cout << evens[i]; } cout << endl; return 0; } ``` ## 📝 代码说明 - **分类**：遍历输入，判断奇偶性，分别存入 `odds` 和 `evens` 两个 `vector`。 - **动态确定值域**：用 `min_element` 和 `max_element` 找出各自的最小值和最大值，确保计数数组不会过大。 - **`countingSort` 函数**： - `count` 数组用于统计每个值在 `[minVal, maxVal]` 之间的出现次数。 - 然后按从小到大重建数组，得到排序结果。 - **输出格式**：奇数一行，偶数一行，每个数字用空格分隔，行末换行。 ## 🧪 样例测试 输入： ``` 5 9 5 10 7 2 ``` 输出： ``` 5 7 9 2 10 ``` ## ⚠️ 注意事项 - **计数排序的时间复杂度**为 O(n + k)，其中 k 是值域范围。这里因为范围不大，效率很高。 - 若输入的数字可能非常大（如 10^9），这种方法会导致计数数组过大，此时建议改用 `std::sort`（快速排序）。 - 题目要求**从小到大**输出，计数排序天然满足。 ## 💡 开发建议 - 对于这种简单排序，直接使用 `std::sort` 可能会更简洁，但计数排序体现了**以空间换时间**的思想，适合教学演示。 - 如果值域已知且较小（例如 0~1000），可以提前分配固定大小的计数数组，避免动态查找最值。 - 可以考虑使用 `std::partition` 来一次遍历完成奇偶分离，提高代码简洁性。 ######[AI写代码神器 | 998点数解答 | 2026-08-15 15:32:00]