C++实现非负整数降序排序的完整指南与优化技巧

我来帮你解决这个排序问题。这是一个典型的排序任务，我们可以使用 C++ 的 STL 算法轻松实现。 ## 🛠️ 解决方案 ```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 函数进行排序，greater<int>() 确保从大到小排序 sort(nums.begin(), nums.end(), greater<int>()); // 输出结果 for (int i = 0; i < n; i++) { cout << nums[i]; if (i != n - 1) { cout << " "; } } cout << endl; return 0; } ``` ## 📝 代码详解 ### 1. **头文件说明** - `<iostream>`：用于输入输出操作 - `<vector>`：使用动态数组存储数据 - `<algorithm>`：包含 `sort()` 排序函数 ### 2. **核心排序部分** ```cpp sort(nums.begin(), nums.end(), greater<int>()); ``` - `nums.begin()`：指向容器第一个元素的迭代器 - `nums.end()`：指向容器最后一个元素之后位置的迭代器 - `greater<int>()`：比较函数对象，确保降序排序（从大到小） ### 3. **替代排序方法** **方法一：使用 lambda 表达式（C++11 及以上）** ```cpp sort(nums.begin(), nums.end(), [](int a, int b) { return a > b; // 降序排序 }); ``` **方法二：先升序排序再反转** ```cpp sort(nums.begin(), nums.end()); // 默认升序 reverse(nums.begin(), nums.end()); // 反转得到降序 ``` **方法三：自定义比较函数** ```cpp bool compare(int a, int b) { return a > b; } // 使用 sort(nums.begin(), nums.end(), compare); ``` ## ⚡ 性能优化建议 ### 1. **输入优化** 对于大数据量（n > 10⁵），建议使用快速输入： ```cpp ios::sync_with_stdio(false); cin.tie(nullptr); ``` ### 2. **内存优化** 如果 n 非常大，可以考虑： ```cpp vector<int> nums; nums.reserve(n); // 预分配内存，避免多次扩容 ``` ### 3. **完整优化版本** ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { // 输入输出优化 ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> nums; nums.reserve(n); // 预分配内存 for (int i = 0; i < n; i++) { int num; cin >> num; nums.push_back(num); } // 降序排序 sort(nums.begin(), nums.end(), greater<int>()); // 输出 for (int i = 0; i < n; i++) { cout << nums[i]; if (i != n - 1) cout << ' '; } cout << '\n'; // 使用 '\n' 比 endl 更快 return 0; } ``` ## 🚨 常见错误及避免方法 ### 1. **数组越界** ```cpp // 错误：使用固定大小数组可能越界 int nums[100]; // 如果 n > 100 就会越界 // 正确：使用 vector 动态分配 vector<int> nums(n); ``` ### 2. **忘记处理空格** ```cpp // 错误：最后一个数字后多输出空格 for (int i = 0; i < n; i++) { cout << nums[i] << " "; // 最后会多一个空格 } // 正确：判断是否为最后一个元素 for (int i = 0; i < n; i++) { cout << nums[i]; if (i != n - 1) cout << " "; } ``` ### 3. **排序方向错误** ```cpp // 错误：默认是升序排序 sort(nums.begin(), nums.end()); // 从小到大 // 正确：添加比较函数实现降序 sort(nums.begin(), nums.end(), greater<int>()); ``` ## 📊 不同排序方法比较 | 方法 | 时间复杂度 | 空间复杂度 | 适用场景 | |------|------------|------------|----------| | `sort()` + `greater` | O(n log n) | O(1) | 通用场景，推荐使用 | | 先升序再反转 | O(n log n) | O(1) | 代码简单易懂 | | 手写快速排序 | O(n log n) | O(log n) | 学习算法原理 | | 计数排序 | O(n + k) | O(k) | 数值范围有限时 | ## 🔧 扩展功能 ### 1. **处理大整数** 如果数字可能超过 int 范围： ```cpp vector<long long> nums(n); // 使用 long long ``` ### 2. **去重后排序** ```cpp sort(nums.begin(), nums.end(), greater<int>()); // 使用 unique 和 erase 去重 nums.erase(unique(nums.begin(), nums.end()), nums.end()); ``` ### 3. **文件输入输出** ```cpp freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); ``` ## 📚 学习资源推荐 1. **C++ 参考文档** - [cppreference.com](https://en.cppreference.com/) - 最全面的 C++ 参考 - [cplusplus.com](http://www.cplusplus.com/) - 初学者友好 2. **算法学习** - 《算法导论》- 经典算法教材 - LeetCode - 在线刷题平台 3. **STL 深入学习** - 《Effective STL》- Scott Meyers - 《C++ Standard Library》- Nicolai Josuttis ## 💡 开发建议 1. **代码规范** - 使用有意义的变量名 - 添加必要的注释 - 保持一致的代码风格 2. **测试用例** ```cpp // 测试边界情况 // 1. n = 0 或 1 // 2. 所有数字相同 // 3. 已经有序的序列 // 4. 包含最大/最小整数值 ``` 3. **错误处理** ```cpp if (n <= 0) { cout << "Invalid input" << endl; return 1; } ``` 4. **性能考虑** - 对于小规模数据（n < 100），各种方法差异不大 - 对于大规模数据，优先使用 STL 的 `sort()` - 考虑使用更快的输入输出方式 这个解决方案简洁高效，利用了 C++ STL 的强大功能，适合各种规模的输入数据。 ######[AI写代码神器 | 1596点数解答 | 2026-03-08 14:08:57]