PHP排序算法系列之桶排序详解

桶排序

桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，事变的道理是将数组分到有限数目的桶里。每个桶再个体排序（有也许再行使此外排序算法或是以递归方法继承行使桶排序举办排序）。桶排序是鸽巢排序的一种归纳功效。当要被排序的数组内的数值是匀称分派的时辰，桶排序行使线性时刻（Θ(n)）。但桶排序并不是较量排序，他不受到O(n log n)下限的影响。

道理

配置一个定量的数组看成空桶子。 寻访序列，而且把项目一个一个放到对应的桶子去。 对每个不是空的桶子举办排序。 从不是空的桶子里把项目再放回原本的序列中。

举例

假定待排数字[6 2 4 1 5 9]

筹备10个空桶,最大数个空桶 [0 0 0 0 0 0 0 0 0 0] 空桶 [0 1 2 3 4 5 6 7 8 9] 桶编号(现实不存在)

1. 次序从待排数组中取出数字,起首6被取出,然后把6入6号桶,这个进程相同这样:空桶[ 待排数组[ 0 ] ] = 待排数组[ 0 ]

[6 2 4 1 5 9] 待排数组 [0 0 0 0 0 0 6 0 0 0] 空桶 [0 1 2 3 4 5 6 7 8 9] 桶编号(现实不存在)

2. 次序从待排数组中取出下一个数字,此时2被取出,将其放入2号桶,是几就放几号桶

[6 2 4 1 5 9] 待排数组 [0 0 2 0 0 0 6 0 0 0] 空桶 [0 1 2 3 4 5 6 7 8 9] 桶编号(现实不存在)

3,4,5,6省略,进程一样,所有入桶后酿成下边这样

[6 2 4 1 5 9] 待排数组 [0 1 2 0 4 5 6 0 0 9] 空桶 [0 1 2 3 4 5 6 7 8 9] 桶编号(现实不存在) 0暗示空桶,跳过,次序取出即可:1 2 4 5 6 9

PHP代码实现

以上就是本文的所有内容，但愿对各人的进修有所辅佐，也但愿各人多多支持编程之家。

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!