桶排序(Bucket Sort)，是一种时间复杂度为O(n)的排序。画外音：百度“桶排序”，很多文章是错误的，本文内容与《算法导论》中的桶排序保持一致。桶排序的适用范围是，待排序的元素能够均匀分布在某一个范围[MIN, MAX]之间。画外音：很多业务场景是符合这一场景，待排序的元素在某一范围内，且是均匀分布的。（1）扫描待排序数据A[N]，对于元素A[i]，放入对应的桶X；（2）A[i]放入桶X，如果桶X已经有了若干元素，使用插入排序，将arr[i]放到桶内合适的位置；（2）插入排序是稳定的，因此桶内元素顺序也是稳定的；当arr[N]中的所有元素，都按照上述步骤放入对应的桶后，就完成了全量的排序。bucket_sort(A[N]){
for i =1 to n{
将A[i]放入对应的桶B[X];
使用插入排序，将A[i]插入到B[X]中正确的位置;
}
将B[X]中的所有元素，按顺序合并，排序完毕;
}
{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]的元素链表。（3）扫描所有元素之后，元素被放到了自己对应的桶里；例如，标红的元素66, 67, 62最终会在一个桶里，并且使用插入排序桶内保持有序。（3）桶排序，适用于数据均匀分布在一个区间内的场景；架构师之路-分享可落地的技术文章