桶排序 bucket sort

     与计数排序类似，桶排序也做了某种假设。计数排序假设输入是一个小范围内的整数。桶排序假设输入元素均匀而独立的分布在区间 [0,1)上。

 

排序思想

     把区间划分成n个大小相同的子区间，或称为桶。然后将n个输入元素分布的各个桶中去。先对各个桶中的数进行排序，然后按次序把各桶中的数据列出来即可。

     （因为输入元素均匀而独立的分布在区间 [0,1)上，所以不会出现很多数落在一个桶中的情况）

 

 

BucketSort(A)

1   n ← A.length

2   for  i ← 1  to n

3          do insert  A[i] into list B[ ⌊n A [i]⌋ ]

4   for  i ← 0  to n - 1

5          do sort list B[i] with insertion sort

6  concatenate the lists  B[0],  B[1], . . ., B[n - 1] together in order

 

示例：

 

运行时间

　　桶排序的运行时间为 Θ(n)+n*O(2-1/n)=

Θ(n)  ，所以桶排序以线性期望时间运行。