C++ 实现计数排序：对 1 - 5000 范围内不重复数字从小到大排序

```cpp #include <iostream> using namespace std; const int MAX_VALUE = 5000; int main() { int n; cin >> n; // 用于计数的数组，初始化为 0 int count[MAX_VALUE + 1] = {0}; // 读取 n 个整数，并统计每个数出现的次数 for (int i = 0; i < n; i++) { int num; cin >> num; count[num]++; } // 输出排序后的结果 for (int i = 1; i <= MAX_VALUE; i++) { for (int j = 0; j < count[i]; j++) { cout << i; if (i < MAX_VALUE || j < count[i] - 1) { cout << " "; } } } cout << endl; return 0; } ``` ### 代码解释： - 定义常量 `MAX_VALUE` 为 5000，这是输入数字的最大值。 - 读取输入的整数 `n`，表示数字的个数。 - 创建一个长度为 `MAX_VALUE + 1` 的数组 `count`，用于统计每个数字出现的次数，初始值都为 0。 - 通过循环读取 `n` 个整数，每读取一个数字，就在 `count` 数组对应位置上加 1。 - 遍历 `count` 数组，对于每个出现的数字，按照其出现的次数输出该数字，同时保证相邻数字间用空格分隔。 ### 复杂度分析： - **时间复杂度**：$O(n + k)$，其中 $n$ 是输入数字的个数，$k$ 是数字的最大值（这里为 5000）。 - **空间复杂度**：$O(k)$，主要用于存储计数数组。 ######[AI问答 | 460点数解答 | 2026-05-23 20:21:24]