基数排序的原理究竟是怎样的复杂机制，竟能实现高效的多关键字排序？

本文共计927个文字，预计阅读时间需要4分钟。

基排序是一种基于比较的整数排序算法，它是对桶排序的一种扩展。基本原理是将整数分割成不同的位数，然后按位比较，从而完成排序。具体来说，是将整数位分隔成不同的数字，然后按照每个数字的值进行排序。从基本排序的描述可以看出，排序的结果如下：

基数排序是桶排序的一种扩展使用，同样是一种非比较的整数排序算法，其原理是将整数位数切割成不同的数字，然后按每个位数分别比较。 详细描述

从基数排序的描述可以看得出，其适用于整数，但是，整数也可以表达字符串（比如名字或时间）和特定格式的浮点数，因此基数排序并不只是适用于整数。

基数排序详细的执行步骤如下：

1. 首先准备 10 个桶，分别用于存储所在位数为 0 ~ 9 的数；
2. 提取出序列中元素的个位，将该元素移动到对应个位所属的桶内；
3. 重复执行第 2 步，从个位、十位、百位直到最大元素的最大位数，没有所在位时赋为 0；
4. 执行完第 3 步，组合每个桶内的元素成有序序列。

算法图解

问题解疑 基数排序的复杂度是多少？

基数排序的时间复杂度和待排序序列的最大位数有关系，由于需要对每一个位数遍历一次序列，基数排序的时间复杂度是 \(O(n \times k)\)，其中 k 是最大位数。

基数排序的空间复杂度是 \(O(n+k)\)，其中 k 是桶的数量。