python之基数排序 python之基数排序的实现
Morbidmuse 人气:0算法思想
插入\交换\选择\归并类的排序算法都需要通过比较关键字的大小来完成排序.因为存在两两比较所以这一类的排序方法在最好情况下能达到的复杂度是O(n*logn),如快速排序\堆排序\归并排序.在一般情况下和最坏情况下复杂度更是达到O(n**2).
为了降低复杂度,就有牛人想出了分配收集排序方法,稍后分析它的时间复杂度能到达O(n),
而基数排序就是一种典型的搜集分配收集排序方法.基数排序时一种借助于多关键字排序的思想对单关键字排序的方法.其基本思想是通过对排序记录进行若干趟(有几个关键字就几趟)"分配"与"收集"来实现排序.
如:
1. 对整数排序,建立编号0-9(10进制的基数)10个桶,用于装对应位为编号的记录.先将待排序序列分配按'个位'数字分配到10各桶中,然后将桶按从小到大的顺序串接起来.
2.将上一步的结果再按'十位''数字分配到10各桶中,然后将桶按从小到大的顺序串接起来.
3. 将上一步的结果再按'百位''数字分配到10各桶中,然后将桶按从小到大的顺序串接起来.
4.如果还有千位\万位.重复以上步骤,直到完成最高位的分配与收集,排序结束.
动图示例:(转自菜鸟教程:1.10 基数排序 | 菜鸟教程 (runoob.com))
算法实现
1.本实现借助队列的数据结构,所以先来定义一个队列
# Bradley N. Miller, David L. Ranum
# Introduction to Data Structures and Algorithms in Python
# Copyright 2005
#
#queue.py
class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0,item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
2.处理输入数据
将一个列表作为输入,将每一个记录处理为具有相同位数的字符串(用字符串类型时为了方便处理)
def inDataProcess(lis):
max_lengh = max([len(lis[i]) for i in range(len(lis))]) # 查询记录中最长的字符串
return [x.zfill(max_lengh) for x in lis] # 将每一个记录都通过添加前导0的方式转化为一样的长度
3.基数排序主函数
def radixSort(seq:list):
source_data = inDataProcess(seq) # 输入处理
res = [] # 用于保存结果列表
big_queue = Queue() # 用于转化的队列
for ele in source_data:
big_queue.enqueue(ele)
for i in range(len(source_data[0])-1,-1,-1):
buckets = [] # 用于保存每一趟的10各基数桶
for num in range(10): # 建立10个基数桶
bucket = Queue()
buckets.append(bucket)
# 在基数桶中插入数据
while not big_queue.isEmpty():
currentEle = big_queue.dequeue() # 大队列中出队一个元素
index = int(currentEle[i]) # 根据元素对应位上的值添加进对应的基数桶中
buckets[index].enqueue(currentEle)
# 把基数桶串联起来
new_big_queue = Queue()
for bucket in buckets:
while not bucket.isEmpty():
out = bucket.dequeue()
new_big_queue.enqueue(out)
# print(new_big_queue.size())
# 修改big_queue
big_queue = new_big_queue
# 将大队列中的元素保存到结果列表中
while not big_queue.isEmpty():
res.append(big_queue.dequeue().lstrip('0')) # 利用lstrip('0')去掉前导0
return res
4.测试及结果
if __name__ == '__main__':
lis = [20,101,39,431,58,600,8,4,999,634,157,199,208,138,389,691,400,932,856,843,401,923]
lis = [str(i) for i in lis]
print(radixSort(lis))
''' 结果>>>['4', '8', '20', '39', '58', '101', '138', '157', '199', '208', '389', '400', '401', '431', '600', '634', '691',
'843', '856', '923', '932', '999']'''
算法分析
1）时间复杂度
对于n个记录（假设每个记录含d个关键字，每个关键字的取值范围为rd个值）进行链式基数排序时，每一趟分配的时间复杂度为O(n)，每一趟收集的时间复杂度为O(rd)，整个排序需进行d趟分配和收集，所以时间复杂度为O(d(n+rd))。
（2）空间复杂度
所需辅助空间为2rd个队列指针，另外由于需用链表做存储结构，则相对于其他以顺序结构存储记录的排序方法而言，还增加了n个指针域的空间，所以空间复杂度为O(n+rd)。
算法的特征
（1）是稳定排序。
（2）可用于链式结构，也可用于顺序结构。
（3）时间复杂度可以突破基于关键字比较一类方法的下界O(nlog2n)，达到O(n)。
（4）基数排序使用条件有严格的要求：需要知道各级关键字的主次关系和各级关键字的取值范围。
ref:
1.严蔚敏等<<数据结构C语言版(第二版)>>
2.Bradley N. Miller, David L. Ranum <<Introduction to Data Structures and Algorithms in Python>>
加载全部内容