PHP 排序整數演算法 - Radix sort 實做

PHP 排序有 sortksort... 等等一堆可以使用, 也都可以拿來排序整數, 速度不一定會比這個演算法慢, 請自行注意使用~ 🙂

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


關於 Tsung

對新奇的事物都很有興趣, 喜歡簡單的東西, 過簡單的生活.
本篇發表於 Programming 並標籤為 , 。將永久鏈結加入書籤。

PHP 排序整數演算法 - Radix sort 實做 有 1 則回應

  1. leafwind 說道:

    偶然 google 發現這篇文章,看到來源網站有人回應,這個演算法應該是叫 counting sort。radix sort 是對特定的基底(radix)的每個 digit 做排序,概念有點類似,但是 counting sort 完全沒有「比較」的過程,取而代之的是需要更大的額外空間

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料