常見的經(jīng)典非比較類排序算法有計(jì)數(shù)排序与涡、桶排序。區(qū)別于比較類排序持偏，非比較類排序利用額外的內(nèi)存空間實(shí)現(xiàn)更快排序驼卖，算法以線性時(shí)間運(yùn)行，時(shí)間復(fù)雜度突破O(nlog2n)鸿秆。
<輸入的最好方式就是輸出>酌畜，本著學(xué)習(xí)的態(tài)度表達(dá)一下自己淺顯的理解。下面主要介紹每種算法的中心思想卿叽，具體的代碼實(shí)現(xiàn)(PHP)桥胞，并分析對(duì)應(yīng)的時(shí)間復(fù)雜度和空間復(fù)雜度。
1.計(jì)數(shù)排序
計(jì)數(shù)排序的基本思路：開辟一個(gè)新的存儲(chǔ)空間考婴，將待排數(shù)組的元素值作為key贩虾，出現(xiàn)的次數(shù)作為value存儲(chǔ)，從最小值到最大值進(jìn)行遍歷沥阱，取出對(duì)應(yīng)空間的值缎罢，放入最后的結(jié)果數(shù)組，完成排序考杉。
代碼如下：
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;
}
}
//構(gòu)造計(jì)數(shù)的數(shù)組策精，考慮重復(fù)項(xiàng)
//這里用到的是php的數(shù)組結(jié)構(gòu)，不是嚴(yán)格意義上的數(shù)組奔则，可以視為鍵值對(duì)
foreach ($arr as $v) {
if (!isset($bucket[$v])) {
$bucket[($v)] = 0;//初始化元素次數(shù)
}
$bucket[$v]++;
}
//構(gòu)造排序結(jié)果
for ($i = $min; $i <= $max; $i++) {
while (isset($bucket[$i]) && $bucket[$i] > 0) {
array_push($result, $i);//放入結(jié)果數(shù)組
$bucket[$i]--;//重復(fù)項(xiàng)減1
}
}
return $result;
}
注意點(diǎn)：在構(gòu)造計(jì)數(shù)數(shù)組時(shí)蛮寂，由于代碼使用的是php語言，在php世界里數(shù)組不是嚴(yán)格意義上的數(shù)組易茬，而是一個(gè)關(guān)于鍵值對(duì)的字典酬蹋，所以我這邊處理起來比較簡單及老。
其他語言這邊應(yīng)該自行調(diào)整：以java為例，需要?jiǎng)?chuàng)建一個(gè)指定長度的數(shù)組范抓，長度len=max-min+1(數(shù)組元素最值);另外由于數(shù)組下標(biāo)為非負(fù)整數(shù)骄恶，而待排數(shù)組元素存在負(fù)數(shù)情況，因此需要做差值轉(zhuǎn)換：將下標(biāo)$i取元素值與最小值的差值存儲(chǔ)匕垫，最后取出時(shí)進(jìn)行轉(zhuǎn)換即可僧鲁。
記憶關(guān)鍵詞：計(jì)數(shù)空間、有序取出
性能分析：時(shí)間復(fù)雜度O(n+k)象泵，空間復(fù)雜度為O(n+k)寞秃；其中n為數(shù)組長度，k為數(shù)組范圍偶惠。
可以看出春寿，如果k值非常大，即使數(shù)組長度小忽孽，會(huì)浪費(fèi)許多空間绑改，同時(shí)也需要浪費(fèi)時(shí)間遍歷它們。
2.桶排序
桶排序是計(jì)數(shù)排序的升級(jí)版兄一，主要區(qū)別在于計(jì)數(shù)排序的存儲(chǔ)空間是數(shù)組厘线，而桶排序的存儲(chǔ)空間是鍵值對(duì)，依賴于函數(shù)的映射關(guān)系出革。桶排序的核心在于映射函數(shù)的確定造壮，算法思路：指定bucket_size作為桶大小，利用它確定桶的數(shù)量蹋盆，數(shù)組元素根據(jù)元素值的映射關(guān)系存到指定桶中费薄。最后每個(gè)桶按照排序算法對(duì)桶內(nèi)元素進(jìn)行排序，放入結(jié)果數(shù)組中栖雾。
代碼如下
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;
}
}
//獲取桶個(gè)數(shù)
$bucketCount = intval($max - $min / $bucketSize) + 1;
//數(shù)組元素入桶
foreach ($arr as $item) {
$key = intval(($item - $min) / $bucketCount);//根據(jù)映射關(guān)系每個(gè)桶存儲(chǔ)相應(yīng)元素
$bucket[$key][] = $item;
}
//對(duì)每個(gè)桶進(jìn)行排序楞抡，并放入結(jié)果
foreach ($bucket as $item) {
$item = insertSort($item);//采用插入排序?qū)ν皟?nèi)元素排序
//放入最終結(jié)果集
foreach ($item as $value) {
array_push($result, $value);
}
}
return $result;
}
從代碼可以看出，桶排序的速度依賴于析藕，桶大小的確定（bucket_size<=max-min）以及桶內(nèi)元素的排序算法召廷，本例使用的是插入排序。插入排序的算法在下面文章的第四點(diǎn)账胧，比較類排序算法傳送門：http://www.reibang.com/p/7360aa8804d0
記憶關(guān)鍵詞：映射函數(shù)竞慢、桶大小、桶數(shù)量
性能分析：時(shí)間復(fù)雜度O(n+k)治泥，空間復(fù)雜度O(n+k)筹煮；其中n為數(shù)組長度，k為數(shù)組范圍居夹。
