PHP排序算法系列之桶排序详解
发布:smiling 来源: PHP粉丝网 添加日期:2021-08-26 10:42:59 浏览: 评论:0
这篇文章主要为大家详细介绍了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代码实现
- <?php
- function bucket_sort($arr){
- $result=[];
- $length=count($arr);
- //入桶
- for($i=0,$max=$arr[$i];$i<$length;$i++){
- if ($max<$arr[$i]) {
- $max=$arr[$i];
- }
- $bucket[$arr[$i]]=[];
- array_push($bucket[$arr[$i]],$arr[$i]);
- }
- //出桶
- for($i=0;$i<=$max;$i++){
- if(!emptyempty($bucket[$i])){
- $l=count($bucket[$i]);
- for ($j=0; $j <$l ; $j++) {
- $result[]=$bucket[$i][$j];
- }
- }
- }
- return $result;
- }
Tags: PHP排序算法 PHP桶排序
相关文章
- ·PHP中实现冒泡排序和快速排序算法示例(2015-04-04)
- ·PHP 冒泡/快速/选择/插入排序算法实例讲解(2015-12-24)
- ·php四种基础排序算法的运行时间比较(2016-08-25)
- ·php实现的常见排序算法汇总(2021-04-11)
- ·PHP简单选择排序算法实例(2021-05-09)
- ·PHP四种基本排序算法示例(2021-05-22)
- ·PHP版本常用的排序算法汇总(2021-06-30)
- ·PHP排序算法系列之归并排序详解(2021-08-27)
- ·PHP排序算法系列之直接选择排序详解(2021-08-27)
- ·PHP排序算法系列之插入排序详解(2021-08-27)
- ·PHP排序算法之冒泡排序(Bubble Sort)实现方法详解(2021-09-11)
- ·PHP排序算法之直接插入排序(Straight Insertion Sort)实例分析(2021-09-11)
- ·PHP排序算法之基数排序(Radix Sort)实例详解(2021-09-11)
- ·PHP排序算法之快速排序(Quick Sort)及其优化算法详解(2021-09-11)
- ·PHP实现桶排序算法(2021-08-27)
推荐文章
热门文章
最新评论文章
- 写给考虑创业的年轻程序员(10)
- PHP新手上路(一)(7)
- 惹恼程序员的十件事(5)
- PHP邮件发送例子,已测试成功(5)
- 致初学者:PHP比ASP优秀的七个理由(4)
- PHP会被淘汰吗?(4)
- PHP新手上路(四)(4)
- 如何去学习PHP?(2)
- 简单入门级php分页代码(2)
- php中邮箱email 电话等格式的验证(2)