C++作业排序400条0-100区间学生成绩，选bucket sort还是merge sort？

针对你当前的C++作业场景，优先选择基于分桶思想的桶排序（本场景下可以用计数排序实现，属于桶排序的特殊适配版本），相比归并排序优势非常明显。

• 时间效率更高：你的成绩取值范围固定为0~100，仅有101个可能的取值，桶排序可以做到*O(n)的线性时间复杂度，远优于归并排序固定的O(nlogn)*复杂度。哪怕只有400条数据，实际运行速度也更快，没有额外的递归、数组合并操作开销。
• 空间消耗更低：桶排序仅需要申请长度为101的计数数组即可完成排序，额外空间消耗是固定的*O(1)级别；而归并排序需要O(n)*级别的额外辅助空间，空间消耗远高于桶排序。
• 实现成本极低：桶排序逻辑非常简单，仅需要两次遍历即可完成排序：第一次统计每个分数的出现次数，第二次按分数顺序导出结果即可，几乎没有调试成本，作业实现起来不容易出错。而归并排序需要处理递归拆分、有序数组合并的逻辑，边界条件容易写错，没必要增加额外的开发成本。

如果后续需求变更，比如成绩取值范围扩大到无明确上限、或者需要排序的元素不是整数类的离散有限值，再选择通用性更强的归并排序即可，当前场景完全不需要用到归并排序。

#include <vector>
using namespace std;

void sortScores(vector<int>& scores) {
    // 分数范围0~100，共101个可能取值
    int scoreCnt[101] = {0};
    // 第一次遍历：统计每个分数的出现次数
    for (int s : scores) {
        scoreCnt[s]++;
    }
    int pos = 0;
    // 第二次遍历：按从小到大顺序回填排序后的分数
    for (int i = 0; i <= 100; ++i) {
        while (scoreCnt[i]--) {
            scores[pos++] = i;
        }
    }
}

内容的提问来源于stack exchange，提问作者abhiramrp