桶排序（BucketSort），是一种时间复杂度为O(n)的排序。桶排序的适用范围是待排序的元素可以均匀分布在一定范围[MIN,MAX]之间。很多业务场景都符合这个场景。待排序的元素在一定范围内，并且均匀分布。桶排序需要两个辅助空间：（1）第一个辅助空间是桶空间B；(2)第二辅助空间为桶空间B；第二个辅助空间是桶中的元素列表空间；通常，空间复杂度为O(n)。桶排序有两个关键步骤：(1)扫描待排序数据A[N]，将元素A[i]放入对应的桶X中；(2)将A[i]放入桶X中，如果桶X中已经有了几个元素，则使用插入排序将arr[i]放入桶中合适的位置；桶X中的所有元素总是有序的；插入排序是稳定的，所以桶中元素的顺序也是稳定的；当arr[N]中的所有元素按照上述步骤放入相应的桶中时，即完成了全排序。桶排序伪代码为：bucket_sort(A[N]){fori=1ton{将A[i]放入对应的桶B[X]中；使用插入排序将A[i]插入到B[X中的正确位置]；}依次合并B[X]中的所有元素，排序完成；}举个栗子：假设待排序数组均匀分布在[0,99]之间：{5,18,27,33,42,66,90,8,81,47,13,67,9,36,62,22}可以设置10个bucket，申请额外空间bucket[10]作为辅助空间。其中，每个桶bucket[i]用于存储[10*i,10*i+9]的元素列表。如上图所示：(1)待排序数组unsorted[16]；(2)桶空间为buket[10]；(3)扫描完所有元素后，将元素放入对应的桶中；(4)在每个桶中，使用插入排序，保证始终有序；例如，标记为红色的第66、67、62号元素最终会进入一个桶中，并使用插入排序来保持桶中的顺序。最后按顺序输出每个桶，排序完成。桶排序（BucketSort），总结：（1）桶排序是一种复杂度为O(n)的排序；(2)桶排序是稳定排序；(3)BucketSort适用于均匀分布在一个区间内的数据Scene；
