【桶排序】
■桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。
■由于我不是看桶排序而受到启发写得,所以我从我的思路来描述一下我写得内容
1.排序前先建立一个函数,从图表的角度来讲是建立了一条基准线。
2.根据函数求出源数组每一个元素的值对应的在X轴上的位置,即上述描述中的数值地址(相同数值地址即在同一个"桶"内)。
3.对"桶"内的数据进行排序(此处使用的是递归的操作,还可以嵌入其他排序)。
4.根据顺序标记,借助转存数组完成对源数组的排序。
■缺陷
1.递归嘛,总有些麻烦在爆发前不可预料
2.内部排序采用递归并不是最优操作......吧
3.逻辑有点差,所以可能内部排序部分有点混乱,甚至不能完成排序(所以请路过的大佬指点指点)
4.补一张变量声明就明白了
5.欢迎补充
■思路启发
我是写完之后才发现这可能是桶排序的,实际上我写这个排序的一个思路来源于一种借助基准线就数据均值的思想,这种思想在计算均值时效率不高,实际意义不大,但拿到排序这边就成为了桶排序建桶标准,所以有时候可以多留意一些算法,多哪怕实际意义不大,也可以作为拓展思考//ps:我前面写快速排序实际上是受霍夫曼编码的启发(对于先写算法后查资料的行为希望后来者们不要再犯,很累的)