章节五： 线性时间排序
前面介绍的几种排序算法，其排序结果中各元素的次序基于输入元素间的比较，这类排序算法称为比较排序。实验证明：对含有n个元素的一个输入序列，任何比较排序在最坏情况都要用O(nlgn)次比较来进行排序，故合并排序和堆排序是渐近最优的（快排在平均情况下达到此上界）。
接下来我们将讨论三种以线性时间运行的算法（非比较排序，下界O（nlgn）不再适用）：计数排序，基数排序和桶排序。
5.1 计数排序
计数排序假设n个输入元素中的每一个都介于0到k之间的整数，此处k为某个整数，其基本思想就是对每一个输入元素x，确定出小于x的元素个数，就可以把x直接放在他最终输出数组中的位置上。显然其时间复杂度为O(k+n)。该算法另外还需要两个数组：存放排序结果的B【0,...n-1】及提供临时存储区的C【0...k】。
//计数排序 PHP实现
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);
}
由于计数排序的时间性能为O(k+n)，故在实践中，当k=O(n)时，我们常常采用计数排序，这样其运行时间就为O(n)；稳定性排序（这一点很重要，计数排序经常作为基数排序的子过程）。
5.2 基数排序
基数排序（radix sort）是一种用在老式穿卡机上的算法，代码很直观，假设长度为n的数组，每个元素都有d位数字，其中1是最低位，第d位为是最高位。
基数排序 PHP实现：
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 元素位数
foreach ($num_digits as $key => $value) {
if (count($value)!=$max_digits) {
array_pad($num_digits[$key], $max_digits, 0);
}
}
//先按数组低位再按高位排序 键值才是关键哇~~
$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位数，每一个位数有k中取值可能（对于十进制数k=10:0...9），则基数排序算法可以在O(d(n+k))时间对这些数进行排序。
5.3 桶排序
当桶排序(bucket sort)的输入符合均匀分布时，即可以以线性时间运行。桶排序假设输入由一个随机过程产生，该过程将元素均匀的分布在0-1上。其基本思想把区间【0，1）划分成n个相同大小的子区间，或称桶。然后将n个输入分布到各个桶中去，先将各个桶中数进行排序，然后按次序把桶中的元素列出来即可。
即使输入不符合均匀分布，但只要各个桶尺寸的平方和与总的元素数呈线性关系，桶排序依然可以以O(n)线性时间运行。
ps:个人感觉基数排序和桶排序具有先提假设条件，未属主流（存在价值当然不容否定），故并桶排序未给出具体实现，只是总体阐述了原理思想流程。
