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)目再放回原來的序列中。
舉例
假定待排數(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è)過程類似這樣:空桶[ 待排數(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省略,過程一樣,全部入桶后變成下邊這樣
[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表示空桶,跳過,順序取出即可: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類與對(duì)象后期靜態(tài)綁定操作實(shí)例詳解
這篇文章主要介紹了PHP類與對(duì)象后期靜態(tài)綁定操作,結(jié)合實(shí)例形式分析了后期靜態(tài)綁定相關(guān)概念、原理、使用方法及操作注意事項(xiàng),需要的朋友可以參考下2018-12-12php基于curl重寫file_get_contents函數(shù)實(shí)例
這篇文章主要介紹了php基于curl重寫file_get_contents函數(shù)的方法,結(jié)合實(shí)例形式分析了php使用curl重寫file_get_contents函數(shù)實(shí)現(xiàn)屏蔽錯(cuò)誤提示的相關(guān)技巧,需要的朋友可以參考下2016-11-11通過PHP CLI實(shí)現(xiàn)簡(jiǎn)單的數(shù)據(jù)庫實(shí)時(shí)監(jiān)控調(diào)度
繼續(xù)CLI模式試驗(yàn),這次通過使用之前的“帶延時(shí)的死循環(huán)”方法,來實(shí)現(xiàn)個(gè)簡(jiǎn)單的數(shù)據(jù)庫實(shí)時(shí)監(jiān)控調(diào)度功能。2009-07-07php實(shí)現(xiàn)算術(shù)驗(yàn)證碼功能
這篇文章主要為大家詳細(xì)介紹了php實(shí)現(xiàn)算術(shù)驗(yàn)證碼功能,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-12-12php/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