桶排序是一种O(n)时间复杂度的排序算法。
桶排序算法思想：
1、先求出序列的max，min，得到数值区间max-min。2、根据数值区间进行n等分，同时建立n个桶，每个桶按从小到大的顺序存放落在此区间的数字。3、接下来每个桶内进行排序：元素分配入桶后，已经得到大致的顺序了，只剩下桶内的顺序未排。4、排完序再按桶逐个输出即可。我们逐步来分析上面的每一步的耗时：
1、O(n)即可得到max，min。2、O(n)即可建立n个桶并把全部元素放入桶中。3、O(n)即可对所有桶进行桶内排序。🔑🔑4、O(n)即可输出n个排完序的数组。在此只证明第三步即可，其他步O(n)都没有疑问。
我们假设问题条件如下：
1、n个元素 2、m个桶 3、元素分布相对均匀由上可得每个桶元素个数：n/m
我们桶内排序可任意选择一种O(nlogn)的排序算法，桶内元素一般以链表存储，因此可以算出全部桶的计算量：
注释：其中第一个O(n)是用于定位链表元素的时间复杂度。
而当n接近于m时（一般我们设置m=n），log(n/m) ≈ 0 所以上式可化简为O(n)！
我们得到了全部桶桶内排序计算量时间复杂度是O(n)! 所以桶排序时间复杂度是O(n)！
如果对您有帮助的话，请点个赞吧！！ 😋😋
