两分钟彻底搞懂桶排序 _桶排序

文章插图

前言在数据结构与算法的排序中，我们很多人可能更多的熟悉冒泡排序、快速排序、归并排序。可能对堆排序、桶排序、计数排数等比较生疏，其实这个也没啥复杂的，算法的排序中，我们很多人可能更多的熟悉冒泡排序、快速排序、归并排序。可能对堆排序、桶排序、计数排数等比较生疏，其实这个也没啥复杂的，桶排序是所有排序中最简单的排序之一。没毛病老铁，就是最简单的之一。并且同排序和计数排序，基数排序有很多相似和渊源之处。后面会进行对比分析记得先关注！

桶排序思想其实桶排序重要的是它的思想，而不是具体实现，桶排序从字面的意思上看：

桶：若干个桶，说明此类排序将数据放入若干个桶中。
桶：每个桶有容量，桶是有一定容积的容器，所以每个桶中可能有多个元素。
桶：从整体来看，整个排序更希望桶能够更匀称，即既不溢出(太多)又不太少。

但是这些桶跟排序又有什么关系呢？首先先说下桶排序的思想，百度百科是这么说的

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

用通俗易懂的话来理解：

将待排序的序列分到若干个桶中，每个桶内的元素再进行个别排序。
时间复杂度最好可能是线性O(n)，桶排序不是基于比较的排序

当然，桶排序是一种用空间换取时间的排序。
既然是排序，那么最终的结果肯定是从小到大的，桶排序借助桶的位置完成一次初步的排序——将待排序元素分别放至各个桶内。
而我们通常根据待排序元素整除的方法将其较为均匀的放至桶中，如8 5 22 15 28 9 45 42 39 19 27 47 12这个待排序序列，假设放入桶编号的规则为：n/10 。这样首先各个元素就可以直接通过整除的方法放至对应桶中。而右侧所有桶内数据都比左侧的要大！

文章插图

在刚刚放入桶中的时候，各个桶的大小相对可以确定，右侧都比左侧大，但桶内还是无序的，对各个桶内分别进行排序，再依次按照桶的顺序、桶内序列顺序得到一个最终排序的序列。

文章插图

以上就是桶排序在算法上的思想了。如果使用JAVA具体实现的话思路也很简单：用List[]类型的集合数组表示桶，每个List代表一个桶，将数据根据整除得到的值直接放到对应编号的集合里面去，再依次进行排序就可以了。
桶排序算法分析上面讲了桶排序的具体思想，但是你是不是总觉得心理没那么踏实呢，这就完了？总觉得怪怪的是吧？
桶排序确实有很多不一样的地方，无论是算法时间复杂度还是整个算法的流程，都不如啥快排啦、归并啦这些传统排序来的实在。

时间复杂度分析桶排序的时间复杂度到底是多少？
我们假设有n个待排序数字。分到m个桶中，如果分配均匀这样平均每个桶有n/m个元素。首先在这里我郑重说明一下桶排序的算法时间复杂度有两部分组成：