【概述】
基数排序（Radix sort）属于“分配式排序”（distribution sort），它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用。
基数排序方法有两类：按照位数比较顺序的不同，将其分为 LSD（Least significant digital） 和 MSD（Most significant digital）两类。
最高位优先（Most Significant Digit First）法，简称MSD法：先按 k1 排序分组，同一组中记录，关键码 k1 相等，再对各组按 k2 排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码 kd 对各子组排序后。再将各组连接起来，便得到一个有序序列。
最低位优先（Last Significant Digit First）法，简称 LSD 法：先从 kd 开始排序，再对 kd-1 进行排序，依次重复，直到对 k1 排序后便得到一个有序序列。
下图我们针对 LSD 法进行讲解。
【算法思路】
基数排序的思想就是先排好个位，然后排好个位的基础上排十位，以此类推，直到遍历最高位次，排序结束。基数排序不是比较排序，而是通过分配和收集的过程来实现排序。初始化 10 个固定的桶，桶下标为 0-9。

1、将所有待比较数据统一为相同位数长度；
2、按照个位数进行排序；
3、按照十位数进行排序；
4、以此类推，已知到最高位进行排序。这样就得到一个有序序列。

【图解算法】
假设有一个数列 {53, 542, 3, 63, 14, 214, 154, 748, 616} 进行排序的过程如下图所示。

【动画展示】

【时间复杂度】
$O(kn)$，其中 $k$ 是常数，$n$ 为元素个数。
【空间复杂度】
$O(n+k)$。
【稳定性】
稳定。