常见的经典非比较类排序算法有计数排序、桶排序。区别于比较类排序，非比较类排序利用额外的内存空间实现更快排序，算法以线性时间运行，时间复杂度突破O(nlog2n)。
<输入的最好方式就是输出>，本着学习的态度表达一下自己浅显的理解。下面主要介绍每种算法的中心思想，具体的代码实现(PHP)，并分析对应的时间复杂度和空间复杂度。
1.计数排序
计数排序的基本思路：开辟一个新的存储空间，将待排数组的元素值作为key，出现的次数作为value存储，从最小值到最大值进行遍历，取出对应空间的值，放入最后的结果数组，完成排序。
代码如下：
function countSort(array $arr)
{
$bucket = [];
$result = [];
$min = $arr[0];
$max = $arr[0];
//获取最大值和最小值
foreach ($arr as $item) {
if ($item < $min) {
$min = $item;
}
if ($item > $max) {
$max = $item;
}
}
//构造计数的数组，考虑重复项
//这里用到的是php的数组结构，不是严格意义上的数组，可以视为键值对
foreach ($arr as $v) {
if (!isset($bucket[$v])) {
$bucket[($v)] = 0;//初始化元素次数
}
$bucket[$v]++;
}
//构造排序结果
for ($i = $min; $i <= $max; $i++) {
while (isset($bucket[$i]) && $bucket[$i] > 0) {
array_push($result, $i);//放入结果数组
$bucket[$i]--;//重复项减1
}
}
return $result;
}
注意点：在构造计数数组时，由于代码使用的是php语言，在php世界里数组不是严格意义上的数组，而是一个关于键值对的字典，所以我这边处理起来比较简单。
其他语言这边应该自行调整：以java为例，需要创建一个指定长度的数组，长度len=max-min+1(数组元素最值);另外由于数组下标为非负整数，而待排数组元素存在负数情况，因此需要做差值转换：将下标$i取元素值与最小值的差值存储，最后取出时进行转换即可。
记忆关键词：计数空间、有序取出
性能分析：时间复杂度O(n+k)，空间复杂度为O(n+k)；其中n为数组长度，k为数组范围。
可以看出，如果k值非常大，即使数组长度小，会浪费许多空间，同时也需要浪费时间遍历它们。
2.桶排序
桶排序是计数排序的升级版，主要区别在于计数排序的存储空间是数组，而桶排序的存储空间是键值对，依赖于函数的映射关系。桶排序的核心在于映射函数的确定，算法思路：指定bucket_size作为桶大小，利用它确定桶的数量，数组元素根据元素值的映射关系存到指定桶中。最后每个桶按照排序算法对桶内元素进行排序，放入结果数组中。
代码如下
function bucketSort(array $arr, int $bucketSize = BUCKET_SIZE)
{
$bucket = [];
$result = [];
//确定最值
$max = $arr[0];
$min = $arr[0];
foreach ($arr as $item) {
if ($max < $item) {
$max = $item;
}
if ($min > $item) {
$min = $item;
}
}
//获取桶个数
$bucketCount = intval($max - $min / $bucketSize) + 1;
//数组元素入桶
foreach ($arr as $item) {
$key = intval(($item - $min) / $bucketCount);//根据映射关系每个桶存储相应元素
$bucket[$key][] = $item;
}
//对每个桶进行排序，并放入结果
foreach ($bucket as $item) {
$item = insertSort($item);//采用插入排序对桶内元素排序
//放入最终结果集
foreach ($item as $value) {
array_push($result, $value);
}
}
return $result;
}
从代码可以看出，桶排序的速度依赖于，桶大小的确定（bucket_size<=max-min）以及桶内元素的排序算法，本例使用的是插入排序。插入排序的算法在下面文章的第四点，比较类排序算法传送门：https://www.jianshu.com/p/7360aa8804d0
记忆关键词：映射函数、桶大小、桶数量
性能分析：时间复杂度O(n+k)，空间复杂度O(n+k)；其中n为数组长度，k为数组范围。
