学而思的竞赛题库需要按难度对题目进行排序，假设难度是一个整数（1-5级），如何高效实现排序？请分析时间复杂度和空间复杂度，以及如果题目数量很大（如百万级），如何优化？
学而思竞赛教练（C++）难度：中等
答案
1) 【一句话结论】：对于1-5级的整数难度题目排序，最佳方法是计数排序，时间复杂度O(n+k)，空间O(k)，适合小范围整数排序，百万级题目时仍高效（k为难度级别数，此处k=5）。
2) 【原理/概念讲解】：计数排序的核心是将整数难度作为索引，统计每个难度出现的次数。具体步骤：
- 确定最大难度值（如5），创建大小为max+1的计数数组（如
count[0..5]），初始化为0； - 遍历所有题目，对每个题目，
count[题目难度]加1（统计频次）； - 对计数数组做前缀和累加，使每个位置存储该难度及之前难度的总题目数（即排序后该难度的“边界”位置）；
- 从后往前遍历原题目数组，将题目放到结果数组对应位置（根据累加后的位置），并更新计数数组。
类比：给每个难度级别贴“标签”，统计有多少个题目属于该标签，按标签顺序排列，就像整理不同颜色的小球，按颜色分类后从左到右排列，且相同颜色的小球保持原有顺序（稳定）。
3) 【对比与适用场景】：
| 算法 | 时间复杂度（最好/平均/最坏） | 空间复杂度 | 适用场景 | 是否稳定 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(1) | 小规模数据 | 是 |
| 快速排序 | O(nlogn) | O(logn) | 大规模数据，一般用途 | 否（原版） |
| 计数排序 | O(n+k) | O(k) | 难度范围小（如1-5）的整数排序 | 是 |
| 基数排序 | O(d(n+k)) | O(n+k) | 非负整数，位数固定 | 是 |
（注：k为难度级别数，此处k=5，d为位数，d=1）
4) 【示例】：伪代码示例
function sortQuestions(questions):
maxDiff = 5 // 假设难度最大为5
count = array of size (maxDiff+1) filled with 0
for each q in questions:
count[q.difficulty] += 1 // 统计每个难度频次
// 前缀和累加，确定边界
for i from 1 to maxDiff:
count[i] += count[i-1]
// 从后往前遍历，保证稳定
result = array of size len(questions)
for i from len(questions)-1 down to 0:
diff = questions[i].difficulty
result[count[diff] - 1] = questions[i]
count[diff] -= 1
return result
5) 【面试口播版答案】：
面试官您好，对于学而思竞赛题库按难度（1-5级整数）排序，我建议采用计数排序。因为难度是固定的小范围整数，计数排序的时间复杂度是O(n+k)，这里k是难度级别数（5），空间复杂度O(k)，非常高效。具体来说，先统计每个难度出现的次数，然后通过前缀和确定每个难度的边界位置，最后从后往前放置题目，保证排序稳定。对于百万级题目，计数排序的线性时间复杂度比快速排序的O(nlogn)更优，空间开销（k=5）也极小，所以能高效处理大数据量。
6) 【追问清单】：
- 问：如果难度范围不是固定的小整数（如1-1000），计数排序是否还适用？
答：当k（最大难度值）远小于n（题目数）时，计数排序仍高效，但空间复杂度会随k增大而增加，此时可考虑基数排序或归并排序。 - 问：排序是否需要稳定？
答：若题目有相同难度但需保持原有顺序（如题目编号），计数排序是稳定的，因为它从后往前遍历，不改变相同难度元素的相对顺序。 - 问：如何处理题目数量极大但难度分布不均（如大部分题目难度为1，少数为5）？
答：计数排序时间复杂度由n和k决定，即使分布不均，仍为O(n+k)，效率高于快速排序（最坏O(n²)）。 - 问：是否需要考虑内存限制？
答：计数排序需额外空间O(k)，当k=5时空间极小，不影响百万级数据；若k很大，可分块处理或用外部排序优化。
7) 【常见坑/雷区】：
- 坑1：误用快速排序，忽略整数范围，导致时间复杂度分析错误（快速排序平均O(nlogn)，最坏O(n²)，且不稳定）。
- 坑2：空间复杂度分析错误，认为计数排序需O(n)空间，而实际上仅需O(k)。
- 坑3：稳定性误解，认为计数排序不稳定，实际上通过后往前遍历保持稳定性。
- 坑4：当难度范围很大时，直接用计数排序空间过大，误以为必须用其他算法，而忽略了基数排序的适用性。
- 坑5：未考虑大数据量下的时间优化，快速排序的优化（三数取中）可能比计数排序快，但计数排序在整数范围小的情况下更优。