十大排序算法（十）--- 桶排序

桶排序的思想是将待排序的数组分成若干个桶(bucket)，然后对每个桶内的元素使用不同的排序算法进行单独排序。然后递归完成整个数组的排序。桶排序算法适合做分布式排序。桶排序的时间复杂度，跟分割的桶的数量，每一个桶内采用的排序算法，以及待排序数组元素分布的均匀性有关。

下面是桶排序的步骤：

创建n个空的桶。将待排序元素分散到每个桶当中。对每一个桶进行单独排序。读取每一个桶的元素，按序放回原始数组中。

桶排序在数据均匀分布时很有用。比如对分布在0.0 ~ 1. 0之间均匀分布的浮点数进行排序。使用传统的比较排序算法(堆排序，归并排序，快速排序等) ，时间复杂度是O(nlogn)。我们可以获得线性时间复杂度吗? 注意此时计数排序无法使用，因为待排序的元素都是小数。桶排序就可以帮我们实现线性的时间复杂度。

下图展示了对数组A[0.35, 0.83, 0.12, 0.28, 0.52, 0.97, 0.23, 0.16, 0.81]的排序过程。

下面是桶排序的代码实现：

A = [0.35, 0.83, 0.12, 0.28, 0.52, 0.97, 0.23, 0.16, 0.81]

def insertionSort(b):

for i in range(1, len(b)):

up = b[i]

j = i - 1

while j >= 0 and b[j] > up:

b[j + 1] = b[j]

j -= 1

b[j + 1] = up

return b

def bucketSort(x):

arr = []

slot_num = 10

for i in range(slot_num):

arr.append([])

# Put array elements in different buckets

for j in x:

index_b = int(slot_num * j)

arr[index_b].append(j)

# Sort individual buckets

for i in range(slot_num):

arr[i] = insertionSort(arr[i])

# concatenate the result

k = 0

for i in range(slot_num):

for j in range(len(arr[i])):

x[k] = arr[i][j]

k += 1

return x

if __name__=='__main__':

print(bucketSort(A))

将上面的代码保存到一个文本文件，后缀名修改为.py。可以用python解释器执行一下，会输出如下结果：

可以看到，排序正确。