前面介紹的幾種排序算法甥温，其排序結(jié)果中各元素的次序基于輸入元素間的比較，這類排序算法稱為比較排序赶舆。實驗證明：對含有n個元素的一個輸入序列踪栋，任何比較排序在最壞情況都要用O(nlgn)次比較來進行排序，故合并排序和堆排序是漸近最優(yōu)的（快排在平均情況下達到此上界）卧土。
接下來我們將討論三種以線性時間運行的算法（非比較排序惫皱，下界O（nlgn）不再適用）：計數(shù)排序，基數(shù)排序和桶排序尤莺。
5.1 計數(shù)排序
計數(shù)排序假設n個輸入元素中的每一個都介于0到k之間的整數(shù)旅敷，此處k為某個整數(shù)，其基本思想就是對每一個輸入元素x颤霎，確定出小于x的元素個數(shù)媳谁，就可以把x直接放在他最終輸出數(shù)組中的位置上涂滴。顯然其時間復雜度為O(k+n)。該算法另外還需要兩個數(shù)組：存放排序結(jié)果的B【0,...n-1】及提供臨時存儲區(qū)的C【0...k】韩脑。
//計數(shù)排序 ?PHP實現(xiàn)
function counting_sort($array=array(),$k){
? ? for ($i=0; $i <=$k ; $i++) {
? ? ? ? $count_arr[]=0;
? ? }
? ? foreach ($array as $value) {
? ? ? ? $count_arr[$value]++;
? ? }
? ? for ($i=1; $i <=$k ; $i++) {
? ? ? ? $count_arr[$i]+=$count_arr[$i-1];
? ? }
? ? for ($i=count($array)-1; $i>=0; $i--) {
? ? ? ? $result[$count_arr[$array[$i]]]=$array[$i];
? ? ? ? $count_arr[$array[$i]]--;
? ? }
?return ksort($result);
}
由于計數(shù)排序的時間性能為O(k+n)氢妈，故在實踐中，當k=O(n)時段多，我們常常采用計數(shù)排序首量，這樣其運行時間就為O(n)；穩(wěn)定性排序（這一點很重要进苍，計數(shù)排序經(jīng)常作為基數(shù)排序的子過程）加缘。
5.2 基數(shù)排序
基數(shù)排序（radix sort）是一種用在老式穿卡機上的算法，代碼很直觀觉啊，假設長度為n的數(shù)組拣宏，每個元素都有d位數(shù)字，其中1是最低位杠人，第d位為是最高位勋乾。
基數(shù)排序 PHP實現(xiàn)：
function getEachValOfNum($key){
? ? $divide=(int)$key;
? ? static $max_digits=1;? $digits=0;
? ?do {
? ? ? ? $arr_digits[]=$divide%10;
? ? ? ? $divide/=10;
? ? ? ? $digits++;
? ? } while ((int)$divide!=0);
? ? if ($max_digits<$digits) {
? ? ? ? $max_digits=$digits;
? ? }
return array('max_digits'=>$max_digits,'digits'=>$arr_digits);
}
function radix_sort($array){
? ? foreach ($array as $value) {
? ? ? ? $arr_digits=getEachValOfNum($value);
? ? ? ? $num_digits[$value]=$arr_digits['digits'];
? ? }
? ? $max_digits=$arr_digits['max_digits'];
//arr_pad 元素位數(shù)
? ? foreach ($num_digits as $key => $value) {
? ? ? ?if (count($value)!=$max_digits) {
? ? ? ? ? array_pad($num_digits[$key], $max_digits, 0);
? ? ? ?}
}
//先按數(shù)組低位再按高位排序 鍵值才是關(guān)鍵哇~~
$result=array_keys($num_digits);
for ($i=0; $i <$max_digits ; $i++) {
? ? foreach ($result as $value) {
? ? ? ? $sort_digit[$value]=$num_digits[$value][$i];
? ? }
? ? asort($sort_digit,SORT_NUMERIC);
? ? $result=array_keys($sort_digit);
}
return result;
}
給定n個d位數(shù)，每一個位數(shù)有k中取值可能（對于十進制數(shù)k=10:0...9）嗡善，則基數(shù)排序算法可以在O(d(n+k))時間對這些數(shù)進行排序辑莫。
5.3 桶排序
當桶排序(bucket sort)的輸入符合均勻分布時，即可以以線性時間運行罩引。桶排序假設輸入由一個隨機過程產(chǎn)生各吨，該過程將元素均勻的分布在0-1上。其基本思想把區(qū)間【0袁铐，1）劃分成n個相同大小的子區(qū)間揭蜒，或稱桶。然后將n個輸入分布到各個桶中去剔桨，先將各個桶中數(shù)進行排序屉更，然后按次序把桶中的元素列出來即可。
即使輸入不符合均勻分布洒缀，但只要各個桶尺寸的平方和與總的元素數(shù)呈線性關(guān)系偶垮，桶排序依然可以以O(n)線性時間運行。
ps:個人感覺基數(shù)排序和桶排序具有先提假設條件帝洪，未屬主流（存在價值當然不容否定），故并桶排序未給出具體實現(xiàn)脚猾，只是總體闡述了原理思想流程葱峡。
