基数排序 #
1. 基数排序算法思想 #
基数排序(Radix Sort)基本思想:
将整数按位数切割成不同的数字,然后按每个位数分别比较进行排序。
2. 基数排序算法步骤 #
基数排序算法可以采用「最低位优先法(Least Significant Digit First)」或者「最高位优先法(Most Significant Digit first)」。最常用的是「最低位优先法」。
下面我们以最低位优先法为例,讲解一下算法步骤。
- 遍历数组元素,获取数组最大值元素,并取得位数。
- 定义一个长度为
10
的桶buckets
,分别代表0 ~ 9
这10
位数字。 - 以个位元素为索引,根据数组元素个位上的值,将数组元素存入对应数字的桶中。
- 清空原始数组,并从桶中依次取出对应元素,重新加入到原始数组中。
- 之后分别以十位,百位,…,最大值元素的最高位为索引,根据元素对应位上的数字,存入对应数字的桶中。并合并数组,完成排序。
3. 基数排序动画演示 #
- 初始序列为
[32, 1, 10, 96, 57, 7, 62, 47, 82, 25, 79, 5]
,序列所有元素的最大位数为2
。 - 以个位为索引,根据元素个位上的数字,将其分别存入到
0
~9
这10
个桶中。 - 清空原始数组,并从桶中依次取出对应元素,重新加入到原始数组中。此时序列变为
[10, 1, 32, 62, 82, 25, 5, 96, 57, 7, 47, 79]
。 - 以十位为索引,根据元素十位上的数字,将其分别存入到
0
~9
这10
个桶中。 - 清空原始数组,并从桶中依次取出对应元素,重新加入到原始数组中。此时序列变为
[1, 5, 7, 10, 25, 32, 47, 57, 62, 79, 82, 96]
,完成排序。
4. 基数排序算法分析 #
- 时间复杂度:$O(n \times k)$。其中 $n$ 是待排序元素的个数,$k$ 是数字位数。$k$ 的大小取决于数字位的选择(十进制位、二进制位)和待排序元素所属数据类型全集的大小。
- 空间复杂度:$O(n + k)$。
- 排序稳定性:基数排序是一种 稳定排序算法。
5. 基数排序代码实现 #
|
|