学习动机

基数排序不会直接比较两个数字。它每次按一位数字分组，并使用稳定的辅助排序，因此能够突破比较排序无法突破的 O(n log n) 界限。

为什么要学习基数排序？

• 近似线性时间：它的运行时间为 O(d * (n + k))，其中 d 是数字的位数，k 是基数（这里为 10）。对于位数有上限的数字，这实际上就是 O(n)。
• 稳定：相等的值会保持原有的相对顺序，这正是逐位排序能够正确组合的关键。
• 不同的思路：它说明排序不一定要通过比较来完成。这对于大型整数或固定宽度的键来说，是一个重要的认识。

这种方法也有取舍：它要求键可以拆分成数字（这里是非负整数），并且需要为桶分配一些额外内存。