拜托，面试别再问我桶排序了！！！

排序，拜托面试中考察基本功问的面试比较多的问题。

时间复杂度为O(n)的别再排序，常见的问桶有三种：

基数排序(Radix Sort) 计数排序(Counting Sort) 桶排序(Bucket Sort)

今天，1分钟，排序争取让大家搞懂桶排序。拜托

画外音：百度“桶排序”，面试很多文章是别再错误的，本文内容与《算法导论》中的问桶桶排序保持一致。

桶排序的排序适用范围是，待排序的拜托元素能够均匀分布在某一个范围[MIN, MAX]之间。

画外音：很多业务场景是面试符合这一场景，待排序的别再元素在某一范围内，且是问桶均匀分布的。

桶排序需要两个辅助空间：

***个辅助空间，排序是桶空间B 第二个辅助空间，是桶内的元素链表空间

总的云南idc服务商来说，空间复杂度是O(n)。

桶排序有两个关键步骤：

扫描待排序数据A[N]，对于元素A[i]，放入对应的桶X 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]的元素链表。

上图所示：

待排序的数组为unsorted[16] 桶空间是buket[10] 扫描所有元素之后，元素被放到了自己对应的桶里 每个桶内，使用插入排序，保证一直是有序的

例如，标红的元素66, 67, 62最终会在一个桶里，并且使用插入排序桶内保持有序。

最终，每个桶按照次序输出，排序完毕。

神奇不神奇!!!

桶排序(Bucket Sort)，总结：

桶排序，是一种复杂度为O(n)的排序 桶排序，是一种稳定的排序 桶排序，适用于数据均匀分布在一个区间内的场景

【本文为专栏作者“58沈剑”原创稿件，转载请联系原作者】

戳这里，服务器租用看该作者更多好文

很赞哦!（399）