PHP 排序有 sort、ksort... 等等一堆可以使用, 也都可以拿來排序整數, 速度不一定會比這個演算法慢, 請自行注意使用~ 🙂
Radix sort 演算法說明、實做
Radix sort 的演算法, 非常簡單, 看一次就記起來了, 上次突然想到就實做來玩玩, 跟 Linux shell 的 sort 比速度, 沒有比較快(偶爾會比 sort 快)
Radix sort 的演算法主要 針對"整數數字"做排序, 作法使用空間換取時間, 將數字都塞進陣列(紀錄次數), 最後將陣列依照順序印出即可.
Radix sort 演算法詳細說明可見下述文章:
註: 上述文章也有範例, 下述是之前臨時想到就隨手寫得, 都可以參考玩玩看.
範例程式: vim sort_int.php # 排序 filename.txt
<?php
$data = array();
$max = 0;
$min = 99999;
$fh = fopen('filename.txt', 'r') or die('File can not read.');
if ($fh) {
while ($line = fgets($fh, 10)) {
$i = trim($line);
$data[$i] = isset($data[$i]) ? $data[$i] + 1 : 1;
if ($max < $i)
$max = $i;
if ($min > $i)
$min = $i;
}
for ($i = $min; $i <= $max; $i++) {
if (isset($data[$i])) {
for ($j = 0; $j < $data[$i]; $j++)
echo $i . "\n";
}
}
if (!feof($fh)) {
echo "Error: unexpected fgets() fail\n";
}
fclose($fh);
}
?>
執行: php sort_int.php > sort_done.txt
偶然 google 發現這篇文章，看到來源網站有人回應，這個演算法應該是叫 counting sort。radix sort 是對特定的基底（radix）的每個 digit 做排序，概念有點類似，但是 counting sort 完全沒有「比較」的過程，取而代之的是需要更大的額外空間