C++实现整数排序的两种高效方法及开发建议

好的，这是一个非常基础的排序问题。我们可以使用多种方法解决，这里提供 **C++** 的几种常见实现，并给出开发建议。 ## 🧠 问题分析 - 输入：第一行 n（1 < n < 100），第二行 n 个整数（1~1000）。 - 输出：排序后的 n 个数，用空格分隔。 - 数据范围较小，但要求高效、规范。 ## 📌 方案一：使用标准库 `sort`（推荐） 这是最简洁、最安全的方式。 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<int> nums(n); for (int i = 0; i < n; i++) { cin >> nums[i]; } sort(nums.begin(), nums.end()); for (int i = 0; i < n; i++) { if (i > 0) cout << " "; cout << nums[i]; } cout << endl; return 0; } ``` **说明：** - `sort` 使用 **Introsort**（混合快速排序、堆排序、插入排序），平均时间复杂度 O(n log n)。 - 对于 n < 100，性能完全足够。 - 需要包含 `<algorithm>` 头文件。 ## 🧩 方案二：计数排序（利用数据范围 1~1000） 由于数值范围很小，计数排序可以达到 O(n + maxVal) 的时间，对于本题非常高效。 ```cpp #include <iostream> using namespace std; int main() { int n; cin >> n; int count[1001] = {0}; // 因为数值范围 1~1000 for (int i = 0; i < n; i++) { int x; cin >> x; count[x]++; } bool first = true; for (int val = 1; val <= 1000; val++) { for (int k = 0; k < count[val]; k++) { if (!first) cout << " "; cout << val; first = false; } } cout << endl; return 0; } ``` **说明：** - 利用桶的思想，直接统计每个数值的出现次数，然后按顺序输出。 - 时间和空间复杂度均为 O(1000)（实际常数很小）。 - 适合数值范围小且重复多的场景。 ## ⚖️ 方案比较 | 方案 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 | |------|------------|------------|------|------| | 标准库 sort | O(n log n) | O(n) | 通用、简洁 | 对数值范围大的情况不占优势 | | 计数排序 | O(n + 1000) | O(1000) | 极快，常数小 | 仅适用于值域较小的整数 | ## 💡 开发建议 1. **优先使用标准库**：`sort` 是通用解决方案，可读性和维护性最好，应作为默认选择。 2. **注意输入格式**：题目要求第二行有 n 个整数，但并未明确保证换行符位置，使用 `cin` 自动跳过空白字符即可安全处理。 3. **输出格式**：注意相邻数字间 **只有一个空格**，且行末无多余空格，建议使用 `if (i > 0)` 判断或布尔变量控制。 4. **边界情况**：虽然 n > 1，但考虑 n=2 时也能正确排序；如果 n 可能为1，代码也能工作。 5. **性能优化**：对于 n<100 的数据规模，任何排序算法都足够快，不必过度优化，清晰优先。 ## 🧪 测试验证 使用你的样例： ``` 输入： 8 3 3 2 7 7 7 6 8 输出（方案一或二都是）： 2 3 3 6 7 7 7 8 ``` ✅ 符合预期。 > 📚 扩展学习： > - [cppreference - std::sort](https://en.cppreference.com/w/cpp/algorithm/sort) > - [计数排序原理](https://zh.wikipedia.org/wiki/计数排序) ######[AI写代码神器 | 956点数解答 | 2026-08-28 19:13:51]