桶排序

桶排序（Bucket sort）或所謂的箱排序，是一個排序算法，工作的原理是將數(shù)組分到有限數(shù)量的桶里。每個桶再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進行排序）。桶排序是鴿巢排序的一種歸納結(jié)果。當要被排序的數(shù)組內(nèi)的數(shù)值是均勻分配的時候，桶排序使用線性時間（Θ(n)）。但桶排序并不是比較排序，他不受到O(n log n)下限的影響。

原理

設(shè)置一個定量的數(shù)組當作空桶子。
尋訪序列，并且把項目一個一個放到對應的桶子去。
對每個不是空的桶子進行排序。
從不是空的桶子里把項目再放回原來的序列中。

舉例

假定待排數(shù)字[6 2 4 1 5 9]

準備10個空桶,最大數(shù)個空桶
[0 0 0 0 0 0 0 0 0 0] 空桶
[0 1 2 3 4 5 6 7 8 9] 桶編號(實際不存在)

1. 順序從待排數(shù)組中取出數(shù)字,首先6被取出,然后把6入6號桶,這個過程類似這樣:空桶[ 待排數(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] 桶編號(實際不存在)

2. 順序從待排數(shù)組中取出下一個數(shù)字,此時2被取出,將其放入2號桶,是幾就放幾號桶

[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] 桶編號(實際不存在)

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] 桶編號(實際不存在)
0表示空桶,跳過,順序取出即可:1 2 4 5 6 9

PHP代碼實現(xiàn)

 ?phpfunction 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 $j++) { $result[]=$bucket[$i][$j]; return $result;}

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持php 。

PHP排序算法系列之歸并排序詳解_php技巧

PHP排序算法系列之直接選擇排序的詳解

PHP排序算法系列之插入排序的詳解

以上就是PHP排序算法系列之桶排序的詳解的詳細內(nèi)容，PHP教程

鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯(lián)系我們修改或刪除，多謝。