动画 | 什么是桶排序？

淡淡的烟草味﹌ 2023-06-24 15:26 4阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![format_png][]

来源 | 算法无遗策

学过上一篇文章的[计数排序][Link 1]之后，特别是归约化分治处理的计数排序（适用于较离散的非负整数序列）。计数排序的局限比较多，在排序之前需要解决负数和小数的问题，而桶排序不需要考虑这些。

桶排序和计数排序一样，不受O(nlogn)时间复杂度下限的影响，它将待排序序列通过遍历方式分到有限数量的桶中，然后每个桶被单独地排序，不管是使用同一个比较类排序算法或者使用不同的排序算法，或者还是递归地使用桶排序。桶排序可以通过比较方式实现，也可以通过非比较方式实现。

通过比较方式的桶排序分为4步工作步骤：

1.设定合适数量的分桶；

2.遍历待排序序列，将每个元素放入到对应的桶中；

3.对每个非空桶进行合适的排序算法；

4.按顺序访问桶，将桶中的元素依次放回到原序列中对应的位置。

关于如何设置合适数量的分桶，我们这里分为两种：设定简单的分桶和归约化的分桶。

设定简单的分桶

假设我们输入数组\[13, 9, 15, 1, 7, 11, 25, 21, 29, 17, 5\]，求数组中的最大值和最小值，max=29，min=1，设定分桶的情况为max/10– min/10+1=3。所以我们设定合适的数量为3桶，从0开始。数组中第一个元素是13，进行(13 - min) / 10的运算，得2，放入到第3个桶；数组中第2个元素是9，(9 - min) / 10 = 0，放入到第1个桶；依此类推。

分布完之后按顺序访问桶，将桶中的元素依次放回到原序列中对应的位置。

动画：简单分桶

Code：简单分桶

![format_png 1][]

Code：插排

![format_png 2][]

归约化分桶

如果元素之间的大小跨度比较大，例如我们输入\[103, 9, 105, 1, 7, 101, 205, 201, 209, 107, 5\]，按照简单分桶情况的话，它的桶数量是209 / 10 – 1 / 10 + 1 = 21是极为不合理的，中间会浪费掉比较多的空桶。

所以和计数排序的归约化分治一样，桶排序也做归约化分桶，情况设为(array\[i\] - min) / (max - min) \* array.length。

我们采用HashMap的方式记录桶的情况，每次将数组中的元素输入到情况去，得到的分桶值作为key，添加元素的动态数组对象作为value。数组遍历完之后也按顺序访问桶，将桶中的元素依次放回到原序列中对应的位置。

动画：归约分桶

Code：归约化分桶

![format_png 3][]

**-----------------------**

**公众号：五分钟学算法****（ID：CXYxiaowu****）**

**博客：www.cxyxiaowu.com**

**知乎：程序员吴师兄**

**一个正在学习算法的人，致力于将算法讲清楚！**

长按下图二维码关注，和你一起领悟算法的魅力**。**

![format_png 4][]

**戳一下下方的小程序，24 小时一起学算法**

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVFUN2tTdnJpYk9tQW5HeGpGczdaMWhTZjhrbjJQRUlrWTlwaWJWaWJraDZ0SW15WkdEdzZpYnhSNW9ibnZqVWliOXlRYkR6RHpvOWxNaHNhQS82NDA?x-oss-process=image/format,png
[Link 1]: https://blog.csdn.net/kexuanxiu1163/article/details/103080949
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKazVpY3lxT1ZHSG9FVHpTeWVGNFFMZm1ESUlEMldOVU1pY3BGZE5OdEd5VXJtTFl1OGlhWlFkZnFpYzBFb3Z0NVNVR0pocTBSdThzTTFGSHcvNjQw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKazVpY3lxT1ZHSG9FVHpTeWVGNFFMZm1XWjdHSGo5YVlsYXVaZUI4MHdqQ2ljcTFsWmljdG8weFlsYnBkbTlxeFFEV0JubjA2S291YnJ5Zy82NDA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKazVpY3lxT1ZHSG9FVHpTeWVGNFFMZm1Qajl6eGxYV1ZPV0ZxQVR5OThqaWJCQXo4WjZ4NHNKbEROQjVVcFo2YzdkdGliTHVzRE5UekhDQS82NDA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVJnTjYxb1pBaWFiNHpKOE9SbG03ektWY2lhUTFGRFFkSHFpYXA5UjlmTWRVM29BWkxiNEwxWk50dnFzeFFLbGljVkxpY0d4ekZ2NFRmV3BtQS82NDA?x-oss-process=image/format,png