桶排序
桶排序(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; }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
更新日志
- 梁汉文2008-EDMONDHITS48[香港]3CD[WAV+CUE]
- 国风大师纯音系列《童丽-[渭城曲]》1CD[WAV分轨][593.5MB]
- 国风大师纯音系列《许菱子《烧筝2》古筝曲集》1CD[WAV分轨][1.3GB]
- 王子异《1996 Part.2》[320K/MP3][18.29MB]
- 群星.1994-宝丽金最倾情3CD【宝丽金】【WAV+CUE】
- 乐俊亨.2024-同泪【CharioticMusic】【FLAC分轨】
- 何耀珊.2006-收获【华纳】【WAV+CUE】
- 梁汉文1994-壹精选[华星][WAV+CUE]
- 洪荣宏1981-歹路不可行·相思雨(飞跃复刻版)[光美][WAV+CUE]
- 旅行团2015-10Day’s[来福胶泥][WAV+CUE]
- 龙千玉.2011-卡将哟【豪记】【WAV+CUE】
- 蔣志光.1993-多情多寂寞(国专)【BMG】【WAV+CUE】
- 陈慧娴.1996-雪映美白96演唱会2CD(2024环球红馆40复刻系列)【环球】【WAV+CUE】
- 王子异《1996 Part.2》[FLAC/分轨][50.66MB]
- 贵族音乐《古典名曲与轻音乐钢琴 打开宝宝睡眠开关》[320K/MP3][155.91MB]