基数排序: 面试必备算法
最新回答
错在情深
2026-01-20 11:41:41
其具体实现步骤为：首先，将所有待排序的数值统一调整为相同的数位长度，对于数位较短的数值，在其前面补零。接着，从最低位开始，依次进行一次排序。完成从最低位到最高位的排序后，数列将变为有序序列。
基数排序可以采用LSD（Least significant digital）或MSD（Most significant digital）的方式。LSD从键值的最右边开始排序，而MSD则相反，从键值的最左边开始。
基数排序的时间复杂度为O(k * n)，其中n为排序元素个数，k为数字位数。需要注意的是，这并不意味着该时间复杂度一定优于O(nlog n)。k的大小取决于数字位的选择（如比特位数）和待排序数据所属数据类型的全集的大小；k决定了进行多少轮处理，n为每轮处理的操作数目。
以排序n个不同整数为例，假设这些整数以B为底，每位数都有B个不同的数字。尽管有B个不同的数字和B个不同的桶，但在每一轮处理中，判断每个待排序数据项只需要一次计算确定对应数位的值，因此在每一轮处理时都需要平均n次操作来将整数放入合适的桶中。因此，基数排序的平均时间T为：
其中前一项是一个与输入数据无关的常数，当然该项不一定小于log n。
与比较排序相比，基数排序的形式复杂度可能不更小，但由于不进行比较，其基本操作的代价较小。在适当选择B的情况下，k一般不大于log n，因此基数排序通常比基于比较的排序（如快速排序）更快。
动态图展示：
Java代码实现：
热门标签
