PHP中的計數排序演算法實作原理

PHPz
發布: 2023-07-09 10:50:02
原創
973 人瀏覽過

PHP中的計數排序演算法實現原理

計數排序是一種非比較排序演算法,它的基本思想是透過統計每個元素的出現次數,然後根據元素的大小,將其放置到有序的位置。計數排序適用於元素範圍不大,且重複元素較多的情況下,時間複雜度為O(n),是一種高效率的排序演算法。

實作原理:

  1. 首先,遍歷待排序數組,找出最大值和最小值,以決定計數數組的大小。
  2. 建立一個計數數組,長度為最大值和最小值之差加1,並初始化為0。
  3. 再次遍歷待排序數組,統計每個元素出現的次數,並將次數儲存到計數數組。
  4. 對計數陣列進行累加操作,即將目前位置的元素與前一位置的元素求和。
  5. 建立一個臨時數組,長度與待排序數組相同,用於儲存排序結果。
  6. 從後向前遍歷待排序數組,利用計數數組中的累加值,將元素放置到臨時數組中的對應位置。
  7. 將暫存數組中的元素複製到原始數組中,完成排序。

以下是PHP程式碼範例:

function countSort($arr) {
    $min = min($arr); // 寻找最小值
    $max = max($arr); // 寻找最大值
    $count = array_fill($min, $max - $min + 1, 0); // 创建计数数组

    foreach ($arr as $num) {
        $count[$num]++; // 统计每个元素的出现次数
    }

    for ($i = $min + 1; $i <= $max; $i++) {
        $count[$i] += $count[$i - 1]; // 计算累加值
    }

    $temp = array_fill(0, count($arr), 0); // 创建临时数组

    for ($i = count($arr) - 1; $i >= 0; $i--) {
        $temp[--$count[$arr[$i]]] = $arr[$i]; // 将元素放置到临时数组中的相应位置上
    }

    for ($i = 0; $i < count($arr); $i++) {
        $arr[$i] = $temp[$i]; // 将临时数组中的元素复制到原始数组中
    }

    return $arr;
}

// 测试示例
$arr = [8, 3, 5, 4, 7, 6, 1, 6, 4, 4];
$result = countSort($arr);
echo implode(' ', $result); // 输出:1 3 4 4 4 5 6 6 7 8
登入後複製

以上就是PHP中計數排序演算法的實作原理,透過統計每個元素的出現次數,然後根據次數將元素放置到有在序的位置上,實現了對待排序數組的排序。這種演算法適用於元素範圍不大,且重複元素較多的情況下,可以在較短的時間內完成排序操作。

以上是PHP中的計數排序演算法實作原理的詳細內容。更多資訊請關注PHP中文網其他相關文章!

來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
最新問題
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板