桶排序思想

8.桶排序

桶排序 (Bucket sort)是一种排序思想。工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响，受数据状况的影响较大。

1、非基于比较的排序，与被排序的样本的实际数据状况很有关系，所
以实际中并不经常使用
2、时间复杂度O(N)，额外空间复杂度O(N)
3、稳定的排序

计数排序和基数排序是桶排序的实际运用。

桶排序运用（求相邻两数的最大差值）

给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O(N)，且要求不能用非基于比较的排序。