一、基数排序简介
基数排序(Radix Sort)是一种非比较型的排序算法,与桶排序的思想相似,对数据进行分桶和合并。
基数排序将数据按位进行分桶,然后将桶中的数据合并。每次分桶只关注其中一位数据,其他位的数据不管,最大的数据有多少位,就进行多少次分桶和合并。基数排序除了用于对整数进行排序,也可以用于对浮点数、字符串进行排序。
基数排序可以分为最高位优先法和最低位优先法,两种方法的结果相同。
最高位优先(Most Significant Digit first)法,简称MSD法。先按最高位进行分桶,合并,一直到最低位,依次进行分桶和合并,便得到一个有序序列。
最低位优先(Least Significant Digit first)法,简称LSD法。先按最低位进行分桶,合并,一直到最高位,依次进行分桶和合并,便得到一个有序序列。
二、基数排序原理
基数排序的原理如下:
1. 求出待排序列表中的最大值,并求出最大值的位(个十百千...)数,有多少位就需要进行多少轮分桶和合并。
2. 开辟内存空间,创建用于分配数据的桶。整数排序时,每一位的范围都在0~9之间,所以需要创建10个桶。
3. 从数据的个位开始(从最高位开始也可以,结果一样),按个位数对数据进行分桶,不考虑其它位的数据大小。
4. 待排序列表中的所有数据都分桶完成后,将所有桶中的数据进行合并,合并时按先进先出的原则取出桶中的数据。
5. 重复步骤3,4,继续按其他位对前面处理过的数据进行分桶和合并。一直到对每一位数据都进行分桶和合并完成,最终得到一个有序序列,列表排序完成。
以列表 [25, 17, 33, 17, 22, 13, 32, 15, 9, 25, 27, 18] 进行升序排列为例。列表的初始状态如下图。
1. 开辟内存空间,创建用于分配数据的桶。创建0~9的10个桶。
2. 走访待排序列表,按个位数对数据进行分桶。25放入数字为5的桶。
3. 继续走访待排序列表按个位数分桶。17放入数字为7的桶。
4. 继续走访待排序列表按个位数分桶。33放入数字为3的桶。
5. 一直走访完整个待排序列表,将所有数据都放入对应的桶中。
6. 从有数据的桶中将数据取出,进行合并。升序排列时先取数字小的桶,降序反之,每个桶中的数据按添加的顺序取出,先进先出。数字为0和1的桶中没有数据,先取出数字为2的桶中的数据。
7. 继续取出数字为3的桶中的数据。
8. 将所有桶中的数据全部取出。以个位数进行分桶和合并完成,第一轮基数排序结束。
9. 第一轮基数排序已经对个位数进行了排序,得到了一个新的列表。在此基础上,走访此列表中的每一个数据,对它们进行第二轮基数排序,这次按数据的十位数进行分桶和合并。22放入数字为2的桶。
10. 继续走访列表按十位数分桶。32放入数字为3的桶。
11. 继续走访列表按十位数分桶。33放入数字为3的桶。
12. 一直走访完整个列表,将所有数据都放入对应的桶中。
13. 从有数据的桶中将数据取出,进行合并。取数据的方法与按个位数分桶时相同,升序排列时先取数字小的桶,降序反之,每个桶中的数据按添加的顺序取出,先进先出。数字9只有一位,十位为0,所以放在数字为0的桶中,先将其取出。
14. 继续取出数字为1的桶中的数据。
15. 将所有桶中的数据全部取出。以十位数进行分桶和合并完成,第二轮基数排序结束。在本例中,最大的数据只到十位,只需要两轮基数排序就排序完成了,如果最大的数据还有百位千位...,继续按相同的方法进行分桶和合并,直到最高位即可。排序结果如下图。
三、Python实现基数排序
代码语言:javascript复制# coding=utf-8
def radix_sort(array):
max_num = max(array)
place = 1
while max_num > 10**place:
place = 1
for i in range(place):
buckets = [[] for _ in range(10)]
for num in array:
radix = int(num/(10**i) % 10)
buckets[radix].append(num)
j = 0
for k in range(10):
for num in buckets[k]:
array[j] = num
j = 1
return array
if __name__ == '__main__':
array = [25, 17, 33, 17, 22, 13, 32, 15, 9, 25, 27, 18]
print(radix_sort(array))
运行结果:
代码语言:javascript复制[9, 13, 15, 17, 17, 18, 22, 25, 25, 27, 32, 33]
代码中,使用Python内置函数max()求出了待排序列表中的最大值,并求出了最大值的位数place。然后创建了10个桶,从数字的个位数开始,将数据进行分桶,所有数据都分完桶之后,将数据从桶中取出,按顺序重新赋值给待排序列表。
代码中的 i 表示按数据的第 i 位进行分桶,i 从个位一直到最高位,radix 表示分桶时桶对应的数字为 radix,j 表示合并桶中的数据时,将数据赋值给待排序列表中索引 j 的位置。
四、基数排序的时间复杂度和稳定性
1. 时间复杂度
在基数排序中,需要走访待排序列表中的每一个元素进行分桶,列表长度为 n , 然后将每个桶中的数据取出进行合并,一共有 k 个桶,所以进行一轮基数排序的时间复杂度为T(n)=n k,再乘分桶和合并的步骤数(常数,不影响大O记法),得出进行一轮基数排序的时间复杂度为 O(n k) 。当待排序列表中的最大值有 d 位时,需要进行 d 轮基数排序,时间复杂度为 O(d*(n k)) 。
2. 稳定性
在基数排序中,需要将待排序列表中的数据进行分桶和合并。在分桶时,如果有相等的数据,它们一定会被分到同一个桶中,是按先后顺序进入桶中的,在合并桶时,按先进先出的原则,先进桶的数据先出桶,相等数据的相对次序不会发生变化。所以基数排序是一种稳定的排序算法。