第三，基数排序的时间复杂度是多少 ？
最佳情况：T(n) = O(n * k)
最差情况：T(n) = O(n * k)
平均情况：T(n) = O(n * k)
k 是待排序列最大值。
动画
LSD 基数排序动图演示：
5. 解答开篇回过头来看看开篇的思考题：如何根据年龄给 100 万用户排序 ？
你可能会说，我用上一节讲的归并、快排就可以搞定啊！是的，它们也可以完成功能，但是时间复杂度最低也是 O(nlogn)。
有没有更快的排序方法呢 ？以下是参考答案。
实际上，根据年龄给 100 万用户排序，就类似按照成绩给 50 万考生排序。
我们假设年龄的范围最小 1 岁，最大不超过 120 岁。
我们可以遍历这 100 万用户，根据年龄将其划分到这 120 个桶里，然后依次顺序遍历这 120 个桶中的元素。
这样就得到了按照年龄排序的 100 万用户数据。
6. 复杂性对比基数排序 vs 计数排序 vs 桶排序
基数排序有两种方法：
MSD 从高位开始进行排序
LSD 从低位开始进行排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
基数排序：根据键值的每位数字来分配桶；
计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；
复杂性对比
名称 平均 最好 最坏 空间 稳定性 排序方式桶排序 O(n + k) O(n + k) O(n2) O(n + k) Yes Out-place
计数排序 O(n + k) O(n + k) O(n + k) O(k) Yes Out-place
基数排序 O(n * k) O(n * k) O(n * k) O(n + k) Yes Out-place
n: 数据规模
桶排序的时间复杂度可以是多种情况的，取决于桶内的排序。
7. 最后文中所有的代码及测试事例都已经放到我的 GitHub 上了。
觉得有用 ？喜欢就收藏，顺便点个赞吧，你的支持是我最大的鼓励！
参考文章：
菜鸟教程 - 算法系列
线性排序：如何根据年龄给100万用户数据排序？
十大经典排序算法总结（JavaScript 描述）
JS 中可能用得到的全部的排序算法