共计 828 个字符，预计需要花费 3 分钟才能阅读完成。
桶排序 (Bucket Sort)，是一种工夫复杂度为 O(n) 的排序。
桶排序的适用范围是，待排序的元素可能 均匀分布在某一个范畴 [MIN, MAX] 之间。
很多业务场景是合乎这一场景，待排序的元素在某一范畴内，且是均匀分布的
桶排序须要两个辅助空间：
（1）第一个辅助空间，是桶空间 B；
（2）第二个辅助空间，是桶内的元素链表空间；
总的来说，空间复杂度是 O(n)。
桶排序有两个关键步骤：
（1）扫描待排序数据 A[N]，对于元素 A[i]，放入对应的桶 X；
（2）A[i] 放入桶 X，如果桶 X 曾经有了若干元素，应用插入排序，将 arr[i] 放到桶内适合的地位；
桶 X 内的所有元素，是始终有序的；
插入排序是稳固的，因而桶内元素程序也是稳固的；
当 arr[N] 中的所有元素，都依照上述步骤放入对应的桶后，就实现了全量的排序。
桶排序的伪代码是：
bucket_sort(A[N]){
for i =1 to n{将 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[10] 来作为辅助空间。其中，每个桶 bucket[i] 来寄存 [10*i, 10*i+9] 的元素链表。
上图所示：
（1）待排序的数组为 unsorted[16]；
（2）桶空间是 buket[10]；
（3）扫描所有元素之后，元素被放到了本人对应的桶里；
（4）每个桶内，应用插入排序，保障始终是有序的；
例如，标红的元素 66, 67, 62 最终会在一个桶里，并且应用插入排序桶内放弃有序。
最终，每个桶依照 秩序输入，排序结束。
桶排序 (Bucket Sort)，总结：
（1）桶排序，是一种 复杂度为 O(n) 的排序；
（2）桶排序，是一种 稳固的 排序；
（3）桶排序，实用于数据均匀分布在一个区间内的场景；
