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所占的空间由输入数组的最大值确定

改进：

1. 针对存在负数的情况

   # 可对负数排序
   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])]
   

2. 针对存在小数的情况

   # 可对小数排序
   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])]
   

3. 利用传统的逐位进行桶排

   这边想到可以在十行内实现的方法实在是太不易读了，如果你有什么清晰的实现代码的话欢迎留言告知