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 完全沒有「比較」的過程，取而代之的是需要更大的額外空間