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

yipeiwu_com5年前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(!empty($bucket[$i])){
   $l=count($bucket[$i]);
   for ($j=0; $j <$l ; $j++) {
    $result[]=$bucket[$i][$j];
   }
  }
 }
 return $result;
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【宜配屋www.yipeiwu.com】。

相关文章

PHP+Ajax检测用户名或邮件注册时是否已经存在实例教程

PHP+Ajax检测用户名或邮件注册时是否已经存在是论坛或会员系统中常见的一个重要功能。本文就以实例形式简单描述这一功能的实现方法。具体步骤如下: 一、PHP检测页面 check.php...

php简单获取复选框值的方法

本文实例讲述了php简单获取复选框值的方法。分享给大家供大家参考,具体如下: html: <form id="form1" name="form1" method="post"...

PHP实现的迪科斯彻(Dijkstra)最短路径算法实例

PHP实现的迪科斯彻(Dijkstra)最短路径算法实例

本文实例讲述了PHP实现的迪科斯彻(Dijkstra)最短路径算法。分享给大家供大家参考,具体如下: 一、待解决问题 单源最短路径问题,在给定有向图中求一个顶点(单源顶点)到其他所有顶点...

替换php字符串中的单引号为双引号的方法

实例如下: $param = "{'id':'12', 'name':'hi'}"; $new = preg_replace('/\"/', '"', $param); 以上这篇...

PHP进阶学习之依赖注入与Ioc容器详解

PHP进阶学习之依赖注入与Ioc容器详解

本文实例讲述了PHP依赖注入与Ioc容器。分享给大家供大家参考,具体如下: 背景 在很多编程语言(例如java)开发中,程序员在某个类中需要依赖其它类的方法,则通常是new一个依赖类再调...