C++使用计数排序实现奇数偶数分别排序输出

### 🔍问题分析 我们需要从输入中读取 `n` 个正整数，然后将这些数分为奇数和偶数两组，分别使用计数排序对它们进行从小到大排序，最后按要求输出排序后的奇数和偶数。 ### 🚀代码实现 ```cpp #include <iostream> #include <vector> #define MAX_NUM 10000 // 假设输入的最大数不超过10000 using namespace std; // 计数排序函数 vector<int> countingSort(const vector<int>& arr, int max_val) { vector<int> count(max_val + 1, 0); vector<int> sorted_arr(arr.size()); // 统计每个元素的出现次数 for (int num : arr) { count[num]++; } // 计算累积计数 for (int i = 1; i <= max_val; i++) { count[i] += count[i - 1]; } // 构建排序后的数组 for (int i = arr.size() - 1; i >= 0; i--) { sorted_arr[count[arr[i]] - 1] = arr[i]; count[arr[i]]--; } return sorted_arr; } int main() { int n; cin >> n; vector<int> odd_nums; vector<int> even_nums; // 读取输入的正整数并分类为奇数和偶数 for (int i = 0; i < n; i++) { int num; cin >> num; if (num % 2 == 1) { odd_nums.push_back(num); } else { even_nums.push_back(num); } } // 对奇数和偶数分别进行计数排序 vector<int> sorted_odd = countingSort(odd_nums, MAX_NUM); vector<int> sorted_even = countingSort(even_nums, MAX_NUM); // 输出排序后的奇数 for (int i = 0; i < sorted_odd.size(); i++) { if (i > 0) { cout << " "; } cout << sorted_odd[i]; } cout << endl; // 输出排序后的偶数 for (int i = 0; i < sorted_even.size(); i++) { if (i > 0) { cout << " "; } cout << sorted_even[i]; } cout << endl; return 0; } ``` ### 💡代码解释 1. **`countingSort` 函数**：该函数实现了计数排序算法。它接受一个整数向量 `arr` 和一个最大可能值 `max_val` 作为参数，返回排序后的向量。 - 首先，创建一个 `count` 向量，用于统计每个元素的出现次数。 - 然后，计算累积计数，以便确定每个元素在排序后的数组中的位置。 - 根据累积计数构建排序后的数组。 2. **`main` 函数**： - 读取输入的正整数 `n`。 - 创建两个向量 `odd_nums` 和 `even_nums`，分别用于存储奇数和偶数。 - 读取 `n` 个正整数，并将它们分类为奇数和偶数，分别存入对应的向量中。 - 对奇数和偶数向量分别调用 `countingSort` 函数进行排序。 - 输出排序后的奇数和偶数，每行一个向量。 ### 🆙进阶建议 - **错误处理**：在读取输入时，可以添加错误处理代码，以确保输入的合法性，例如 `n` 是否在有效范围内，输入的数是否为正整数等。 - **性能优化**：如果输入的数范围较大，可以考虑动态确定 `MAX_NUM` 的值，避免浪费空间。 - **代码复用**：可以将分类和输出的逻辑封装成独立的函数，提高代码的复用性。 ### 📚学习资源 - [C++ 官方文档](https://en.cppreference.com/w/)：提供了 C++ 语言的详细文档和示例。 - 《C++ Primer》：一本经典的 C++ 学习书籍，适合初学者和有一定基础的开发者。 ######[AI写代码神器 | 1000点数解答 | 2026-08-15 15:33:12]