前言：目录桶排序思想桶排序算法分析时间复杂度，桶排序应用情况，实现一个桶排序结语
前言
在数据结构和算法排序方面，可能很多人都熟悉气泡排序、快速排序和合并排序。 可能在堆叠顺序、桶顺序、数数顺序等方面比较松散，但其实这也并不复杂。桶排序是所有排序中最简单的排序之一。没有怪癖的旧铁是最简单的一种。 另外，桶排序和计数排序、基数排序有很多相似和起源点。 稍后进行比较分析。 请先关注。
桶排序思想其实桶排序是它的思想，而不是具体的实现。 桶排序在字面上是：
桶：多个桶。 表示这样的排序会将数据放入多个桶中。 桶：每桶有容量，桶是具有一定容积的容器，所以每桶可能有多种元素。 桶：总体上看，整个排序都希望桶更均匀。 这意味着溢出和溢出都不会太少。
但这些桶和排序有什么关系呢？
首先，让我谈谈桶排序的思想。 百度百科这样说
结构是将排列分成有限数量的桶。 对每个桶分别排序。 您可以使用其他排序算法，也可以继续使用桶排序递归排序。 桶排序是鸽巢排序的总结结果。 如果要排序的数组中的数值是均匀分配的，则桶排序使用线性时间((n ) )。 但是，桶排序不是比较排序，不受o(nlogn )下限的影响。
用通俗易懂的语言理解：
3358www.Sina.com/时间复杂度宜为线性o(n )。 桶排序当然不是基于比较的排序，将待排序的序列分到若干个桶中，每个桶内的元素再进行个别排序。
既然是排序，最终的结果一定是从小到大，桶的排序按照桶的位置完成最初的排序——，要排序的要素配置在各自的桶中。
我们通常通过用排序对象的要素除尽的方法，将其比较均匀地放入桶中。 例如，要排序的数组8 5 22 15 28 9 45 42 39 19 27 47 12为http://www.Sina.com/n/10。 这样，首先各元素可以用直接整除的方法装入对应的桶中。 右边所有桶里的数据都比左边的大！
刚装桶时，各桶大小可以相对确定，右侧均大于左侧，但桶内无序，将各桶内分别排序，依次按桶序、桶内顺序得到最终排序的序列。
以上就是算法上木桶排序的思想。 如果使用java具体实现的话，想法也很简单。 用List[]型的集合数组表示桶，每个List表示桶。 将数据整除后得到的值直接放入对应的编号集合中，按顺序排序即可。
在对桶排序算法的分析中谈到了桶排序的具体思想，你不是觉得心理上不那么坚定吗？ 这样就结束了吗？ 总觉得很奇怪吧？
铲斗排序确实有很多不同之处。 无论是算法的时间复杂度还是整个算法的流程都比快速排序和合并等传统排序不现实。
时间复杂度分析时段排序的时间复杂度是多少？
假设有n个要排序的数字。 分成m个桶，均匀分配，每桶平均有n/m个元素。 首先，ymdxd在这里说明桶排序算法的时间复杂度有两个部分：
1 .遍历处理每个元素，o(n )层常规遍历2 )每个时段内重新排序的时间复杂度总和对于第一部分，最后排序顺序取值的遍历的o ) n )我想您应该理解。 第二部分可以进行这样的分析。
在桶内元素分配比桶排序是一种用空间换取时间的排序。均匀的情况下，各桶内的时间复杂度为(n/m ) log (n/m ) )。 给定m个桶，时间复杂度为m*(n/m ) log ) n/m )=n ) logn-logm )。
因此，最终分组排序的时间复杂度是o(n ) o(n* )逻辑(logn-logm )；o ) n* )逻辑(logn-logm ) )，其中m是分组的数量。 我们有时也写o (数控)。 其中c=n* ) logn-logm )； 这里达到极限情况n=m时。 可以避免铲斗内的排序。 将数值放入时段后，无需重新排序即可达到o(n )的排序效果。 当然，这是计数排序，稍后请详细了解并记住计数排序后再回顾。
桶排序的适用情况桶排序不像通常的排序那样有限制，桶排序有相当大的限制。假设放入桶编号的规则每个桶都必须避开空桶。 因此，在使用桶排序时，请使用假设每个桶内部使用的排序算法为快速排序
桶的个数和大小都是我们人为设置的
这就是：
实际上，这相当于只使用少量有效的桶来重新排序桶的时间复杂度。 o(nn* ) logn-log m ) ) m指向1，logm去0。 整个复杂度为o (从等级来看为o ) (o(nO(nlogn ) ) nlogn。 即使你看，这种情况也和没有用水桶一样，看起来很快
待排序数列要求偏均匀
不，真的不能。 如果有100000个桶的话，请看
会造成什么情况：这才短短不到100个数，你为了一一映射用100000个空间，空间内容浪费不说，你遍历虽然O(n)也是100000次也比100个的O(nlogn)大上很多啊，真是折了zzdxn又折兵。
所以现在明白前面说的话了吧：数要相对均匀分布，桶的个数也要合理设计。总之桶排序是一种用空间换取时间的排序。在设计桶排序，你需要知道输入数据的上界和下界，看看数据的分布情况，再考虑是否用桶排序，当然如果能用好桶排序，效率还是很高的！
实现一个桶排序在这里用java给大家实现一个桶排序。假设序列为：1 8 7 44 42 46 38 34 33 17 15 16 27 28 24；我们选用5个桶进行桶排序。
import java.util.ArrayList;import java.util.List;//微信公众号：bigsaipublic class test3 {public static void main(String[] args) {int a[]= {1,8,7,44,42,46,38,34,33,17,15,16,27,28,24};List[] buckets=new ArrayList[5];for(int i=0;i<buckets.length;i++)//初始化{buckets[i]=new ArrayList<Integer>();}for(int i=0;i<a.length;i++)//将待排序序列放入对应桶中{int index=a[i]/10;//对应的桶号buckets[index].add(a[i]);}for(int i=0;i<buckets.length;i++)//每个桶内进行排序(使用系统自带快排){buckets[i].sort(null);for(int j=0;j<buckets[i].size();j++)//顺便打印输出{System.out.print(buckets[i].get(j)+" ");}}}}打印结果为：
至此，桶排序就讲完了，当然本文可能有地方讲的不好或者拥有纰漏之处还请大佬指出，后面还会讲解计数排序、基数排序并且将三者进行归纳总结！
笔者微信公众号：bigsai 一个有趣的小伙子，时常会通过公众号和大家做一些有趣的项目和活动，欢迎关注，您的关注是我源源不断的动力。