基数排序实现优化：性能不及std::sort的问题与微优化建议

• 最初在Stack Overflow发布Python版本的基数排序问题，遵照@user24714692建议改用C++实现后提出此问题。
• 实现了支持排序值范围达n²（n为待排列表长度）的基数排序，用于和标准库std::sort（三部分混合排序算法）做性能基准测试。
• 意外发现：即便改用直接访问数组而非哈希表，我的基数排序在大输入规模下仍慢于std::sort。

核心诉求 #

• 基数排序理论时间复杂度为O(n)，std::sort为O(nlogn)，因此认为存在微优化空间。
• 仅为学习目的，不寻求第三方库优化，希望获得易懂的微优化建议，并确认我的代码是否真的为*O(n)*时间复杂度。

已尝试的优化措施 #

• 使用reserve避免push_back的性能损耗，效果尚可。
• 尝试链表实现：用三个数组实现时有效，但用Node类+链表数组实现时无效。

测试相关信息 #

• 编译时已启用-O3优化，测试时间单位为秒，附详细测试数据、实现代码。
• 提供了性能折线图及Time/n分析图，其中std::sort的Time/n表现出意外的常数特性，对此存在疑惑。

内容的提问来源于stack exchange，提问作者FluidMechanics Potential Flows