基数排序是一种非比较排序算法，它将数据按照位数切割成不同的数字，然后按照每个位数分别比较。这种排序方法根据排序的对象不同可以分为 LSD（Least Significant Digit）和 MSD（Most Significant Digit）两种，这里我们主要介绍 LSD 基数排序。
基本思想
将待排序的数值统一表示为同样位数的十进制数，然后从低位向高位依次进行排序，每一位按照一定的比较规则从小到大排序。这一过程称为对数据的一次排序。对所有位均排序完成后，数列就变成了一个有序序列。
算法流程
- 找到最大数，并计算其位数 d
- 对于每一位数，利用桶排序的思想进行排序
- 根据每一位排序的结果重组数据序列
示例说明
假设有一个需要排序的数字序列：[73, 22, 93, 43, 55, 14, 28, 65, 39, 81]。
-
找到最大数，并计算其位数 d
- 最大数为 93，d 为 2
-
对于每一位数，利用桶排序的思想进行排序
- 针对个位数进行排序
- 对于数字序列中的每一个数，按照个位数的值将其分配到一个桶中，并按照桶的顺序输出，得到一个新的序列：[81, 22, 93, 43, 55, 65, 14, 28, 39, 73]
- 针对十位数进行排序
- 对于数字序列中的每一个数，按照十位数的值将其分配到一个桶中，并按照桶的顺序输出，得到一个新的序列：[14, 22, 28, 39, 43, 55, 65, 73, 81, 93]
- 针对个位数进行排序
-
根据每一位排序的结果重组数据序列
- 将第二步得到的序列作为新的序列，此时序列就变成了一个有序序列：[14, 22, 28, 39, 43, 55, 65, 73, 81, 93]
另一个示例是针对字符串排序，假设有一个需要排序的字符串序列：[“ab”, “bb”, “ba”, “cb”, “aa”, “dc”]。
-
找到最大字符串，并计算其位数 d
- 最大字符串为 “dc”，d 为 2
-
对于每一位数，利用桶排序的思想进行排序
- 针对个位数进行排序
- 对于字符串序列中的每一个字符串，按照个位字母的值将其分配到一个桶中，并按照桶的顺序输出，得到一个新的序列：[“cb”, “bb”, “dc”, “aa”, “ab”, “ba”]
- 针对十位数进行排序
- 对于字符串序列中的每一个字符串，按照十位字母的值将其分配到一个桶中，并按照桶的顺序输出，得到一个新的序列：[“aa”, “ab”, “ba”, “bb”, “cb”, “dc”]
- 针对个位数进行排序
-
根据每一位排序的结果重组数据序列
- 将第二步得到的序列作为新的序列，此时序列就变成了一个有序序列：[“aa”, “ab”, “ba”, “bb”, “cb”, “dc”]
代码实现
下面用 Python 代码演示 LSD 基数排序的实现过程。
def radix_sort(nums):
d = len(str(max(nums))) # 找到最大数，并计算其位数 d
for i in range(d):
buckets = [[] for _ in range(10)]
for num in nums:
digit = (num // 10 ** i) % 10 # 计算当前位数的值
buckets[digit].append(num) # 将当前数值分配到对应桶中
nums = [num for bucket in buckets for num in bucket] # 重组数据序列
return nums
使用方法
基数排序适合对于位数不太多的数或字符串进行排序。在使用的过程中，需要注意以下几点：
– 对于数字序列，需要找到最大数并计算其位数 d
– 对于字符串序列，需要找到最大字符串并计算其位数 d，每个字符串的长度一般不超过 d
– 基数排序的时间复杂度是 O(d * n)，其中 d 为最大数或字符串的位数，n 为待排序序列的长度。
建议将该算法作为排序算法中的一种备选，用于对位数不太多的数字或字符串进行排序。