created by Dejavu
- 代码
这里的桶排的写法是利用创建一个长度为输入数组array最大值的临时数组book,然后把array中的值逐一代入book的索引，对应的book数组索引下的值就是数字出现的次数，从而返回book中的非零索引即可
def bucket_sort(array):
if not array:
return False
max_len = max(array)+1
book = [0 for x in range(0,max_len)]
for i in array:
book[i] += 1
return [i for i in range(0,max_len) for j in range(0,book[i])]
- 改进
缺陷：无法排负数，无法排小数，book所占的空间由输入数组的最大值确定
改进：
-
针对存在负数的情况
# 可对负数排序 def bucket_sort(array): if not array: return False offset = min(array) max_len = max(array) - offset + 1 book = [0 for x in range(0,max_len)] for i in array: book[i - offset] += 1 return [i + offset for i in range(0,max_len) for j in range(0,book[i])]
-
针对存在小数的情况
# 可对小数排序 def bucket_sort(array): if not array: return False # 保留两位小数 accuracy = 100. offset = int(min(array) * accuracy) max_len = int(max(array) * accuracy - offset + 1) book = [0 for x in range(0,max_len)] for i in array: book[int(i * accuracy - offset)] += 1 return [(i + offset) / accuracy for i in range(0,max_len) for j in range(0,book[i])]
-
利用传统的逐位进行桶排
这边想到可以在十行内实现的方法实在是太不易读了，如果你有什么清晰的实现代码的话欢迎留言告知
