数据结构与算法 — 10大经典排序算法之桶排序

算法思想

桶排序是计数排序的进级版。它应用了函数的映照关系，高效与否的关键就在于这个映照函数的肯定。桶排序 的工作的原理：假定输入数据服从均匀散布，将数据分到有限数量的桶里，每一个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）文章源自微观生活（93wg.com）微观生活-https://93wg.com/10607.html

算法描写文章源自微观生活（93wg.com）微观生活-https://93wg.com/10607.html

算法图示文章源自微观生活（93wg.com）微观生活-https://93wg.com/10607.html

举例说明，例如输入数据：21，8，6，11，36，50，27，42，0，12。文章源自微观生活（93wg.com）微观生活-https://93wg.com/10607.html

代码示例算法分析文章源自微观生活（93wg.com）微观生活-https://93wg.com/10607.html

桶排序最佳情况下使用线性时间O，桶排序的时间繁杂度，取决与对各个桶之间数据进行排序的时间繁杂度，由于其它部份的时间繁杂度都为O。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间损耗就会增大。文章源自微观生活（93wg.com）微观生活-https://93wg.com/10607.html

桶排序中很重要的一步就是桶的设定了，咱们必需依据输入元素的情况，选择一个恰当的 “getBucketIndex” 算法，使得输入元素能够正确的放入对应的桶内，且保证输入数据能够尽可能均匀的放入不同的桶内。文章源自微观生活（93wg.com）微观生活-https://93wg.com/10607.html

最糟糕糕的情况下，即所有的数据都放入了一个桶内，桶内自排序算法为插入排序，那么其时间繁杂度就为 O 了。文章源自微观生活（93wg.com）微观生活-https://93wg.com/10607.html

其次，咱们可以发现，区间划分的越细，即桶的数量越多，理论上分到每一个桶中的元素就越少，桶内数据的排序就越简单，其时间繁杂度就越接近于线性。文章源自微观生活（93wg.com）微观生活-https://93wg.com/10607.html

极端情况下，就是区间小到只有1，即桶内只寄存一种元素，桶内的元素再也不需要排序，由于它们都是相同的元素，这时候桶排序差不多就以及计数排序同样了。文章源自微观生活（93wg.com）微观生活-https://93wg.com/10607.html

以上就是微观生活（93wg.com）关于“数据结构与算法 -- 10大经典排序算法之桶排序”的详细内容，希望对大家有所帮助！