PHP排序算法系列之桶排序詳解
桶排序
桶排序（Bucket sort）或所謂的箱排序，是一個(gè)排序算法，工作的原理是將數(shù)組分到有限數(shù)量的桶里。每個(gè)桶再個(gè)別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序）。桶排序是鴿巢排序的一種歸納結(jié)果。當(dāng)要被排序的數(shù)組內(nèi)的數(shù)值是均勻分配的時(shí)候，桶排序使用線性時(shí)間（Θ(n)）。但桶排序并不是比較排序，他不受到O(n log n)下限的影響。
原理
設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶子。
尋訪序列，并且把項(xiàng)目一個(gè)一個(gè)放到對(duì)應(yīng)的桶子去。
對(duì)每個(gè)不是空的桶子進(jìn)行排序。
從不是空的桶子里把項(xiàng)目再放回原來(lái)的序列中。
舉例
假定待排數(shù)字[6 2 4 1 5 9]
準(zhǔn)備10個(gè)空桶,最大數(shù)個(gè)空桶
[0 0 0 0 0 0 0 0 0 0] 空桶
[0 1 2 3 4 5 6 7 8 9] 桶編號(hào)(實(shí)際不存在)
1. 順序從待排數(shù)組中取出數(shù)字,首先6被取出,然后把6入6號(hào)桶,這個(gè)過(guò)程類似這樣:空桶[ 待排數(shù)組[ 0 ] ] = 待排數(shù)組[ 0 ]
[6 2 4 1 5 9] 待排數(shù)組
[0 0 0 0 0 0 6 0 0 0] 空桶
[0 1 2 3 4 5 6 7 8 9] 桶編號(hào)(實(shí)際不存在)
2. 順序從待排數(shù)組中取出下一個(gè)數(shù)字,此時(shí)2被取出,將其放入2號(hào)桶,是幾就放幾號(hào)桶
[6 2 4 1 5 9] 待排數(shù)組
[0 0 2 0 0 0 6 0 0 0] 空桶
[0 1 2 3 4 5 6 7 8 9] 桶編號(hào)(實(shí)際不存在)
3,4,5,6省略,過(guò)程一樣,全部入桶后變成下邊這樣
[6 2 4 1 5 9] 待排數(shù)組
[0 1 2 0 4 5 6 0 0 9] 空桶
[0 1 2 3 4 5 6 7 8 9] 桶編號(hào)(實(shí)際不存在)
0表示空桶,跳過(guò),順序取出即可:1 2 4 5 6 9
PHP代碼實(shí)現(xiàn)
<?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;
}
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要介紹了PHP八大設(shè)計(jì)模式案例詳解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
php學(xué)習(xí)筆記之mb_strstr的基本使用
這篇文章主要給大家介紹了關(guān)于php學(xué)習(xí)筆記之mb_strstr的基本使用，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧。2018-02-02
PHP調(diào)用全國(guó)天氣預(yù)報(bào)數(shù)據(jù)接口查詢天氣示例
這篇文章主要介紹了PHP調(diào)用全國(guó)天氣預(yù)報(bào)數(shù)據(jù)接口查詢天氣,涉及第三方平臺(tái)的key申請(qǐng)、接口數(shù)據(jù)調(diào)用及curl相關(guān)操作技巧,需要的朋友可以參考下2019-02-02
php/JS實(shí)現(xiàn)的生成隨機(jī)密碼(驗(yàn)證碼)功能示例
這篇文章主要介紹了php/JS實(shí)現(xiàn)的生成隨機(jī)密碼(驗(yàn)證碼)功能,結(jié)合實(shí)例形式分析了php與javascript隨機(jī)字符串生成相關(guān)的字符串遍歷、隨機(jī)數(shù)生成、編碼轉(zhuǎn)換等操作技巧,需要的朋友可以參考下2019-06-06
通過(guò)Email發(fā)送PHP錯(cuò)誤的方法
這篇文章主要介紹了通過(guò)Email發(fā)送PHP錯(cuò)誤的方法,實(shí)例分析了php錯(cuò)誤的讀取及通過(guò)php發(fā)送Email的相關(guān)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-07-07
實(shí)例解析PHP定時(shí)器的具體實(shí)現(xiàn)
我們?cè)陂_(kāi)發(fā)中常會(huì)需要程序定時(shí)的執(zhí)行一些操作，這時(shí)寫(xiě)一個(gè)簡(jiǎn)潔高效的定時(shí)器就非常有必要，關(guān)于定時(shí)器本文將給大家詳細(xì)的介紹，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值2021-09-09
本篇文章是對(duì)strtr函數(shù)的效率問(wèn)題進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-06-06
php+mysql結(jié)合Ajax實(shí)現(xiàn)點(diǎn)贊功能完整實(shí)例
這篇文章主要介紹了php+mysql結(jié)合Ajax實(shí)現(xiàn)點(diǎn)贊功能,以一個(gè)完整實(shí)例形式詳細(xì)分析了實(shí)現(xiàn)點(diǎn)贊功能中涉及的html頁(yè)面、Ajax功能及php方法的使用技巧,非常具有實(shí)用價(jià)值,需要的朋友可以參考下2015-01-01
這篇文章主要介紹了php簡(jiǎn)單獲取復(fù)選框值的方法,簡(jiǎn)單分析了php以數(shù)組形式傳遞復(fù)選框checkbox值的實(shí)現(xiàn)方法,需要的朋友可以參考下2016-05-05
PHP執(zhí)行Curl時(shí)報(bào)錯(cuò)提示CURL ERROR: Recv failure: Connection reset by
這篇文章主要介紹了PHP執(zhí)行Curl時(shí)報(bào)錯(cuò)提示CURL ERROR: Recv failure: Connection reset by peer的解決方法,需要的朋友可以參考下2014-06-06