经典算法(十)----桶排序----图解法让你快速入门
引言
前面学习了计数排序和基数排序,其实桶排序就是他们的升级版,在这篇文章中主要会说明桶排序的思想,就不放桶排序的代码了,因为桶排序用的较少,至于为啥他用的很少,下面会说。
这篇文章从一下两个角度分析桶排序
- 桶排序的思想
- 桶排序的问题
一、桶排序的思想
假如我们对0.0 0.12 0.18 0.93 0.45 0.76 0.89 0.03 0.55 0.98 0.67 1.0这十二个数排序。桶排序的思想就主要分三步
- 设计好有几个桶,每个桶的范围都为多少
- 对每个桶进行排序
- 按照顺序,把每个桶的数据都取出来
下面看图
我们一共分了四个桶,每个的范围也都提前规定好了。截止到现在,第一步就完成了
第二步就是对每个桶进行排序,这里采取的排序方法可以任选,没有硬性规定。
第三步就是按照桶排序好的顺序,一个个把桶内的数据输出来。
到此为止,桶排序的思想就说完了,思想比较容易理解,但是实现比较困难,下面展开说。
二、桶排序的问题
首先再总结一下流程,
- 求要排序数组的最大值和最小值,根据这两个值,再根据定几个桶,来定每个桶的范围。
- 对每个桶都进行排序。
- 按照顺序输出每个桶的数据
下面说为啥桶排序不常用的原因。
- 每个桶如果用数组存数据,那如果数组不够用怎么办?,因为一组数可能有的很集中,有的很分散,如果数组开大了,那分散的数,就会造成空间浪费。
- 如果每个桶用链表存,那就不用提前开辟空间了,但是又存在了时间问题,因为如果对链表进行排序,只能进行一遍一遍的遍历(访问链表的数据不能随机访问),那时间复杂度就特别大了。
- 如果一个要排序的数据特别集中,比如有1000个数据,结果超过了800个数据在一个桶内,那桶排序的优势更体现不出来了。