PHPにおけるカウンティングソートアルゴリズムの実装原理

PHP におけるカウント ソート アルゴリズムの実装の原則

カウント ソートは非比較ソート アルゴリズムです。その基本的な考え方は、各要素の出現をカウントし、そのサイズに従って要素を配置することです。整然とした位置。カウントソートは、要素の範囲が狭く、繰り返し要素が多い場合に適しており、時間計算量は O(n) で効率的なソートアルゴリズムです。

実装原理:

1. まず、ソートする配列を走査し、最大値と最小値を見つけて、カウント配列のサイズを決定します。
2. 最大値と最小値の差に 1 を加えた長さの count 配列を作成し、0 に初期化します。
3. 並べ替える配列を再度トラバースし、各要素の出現数をカウントし、その数を count 配列に保存します。
4. カウント配列に対して累積演算を実行します。つまり、現在の位置の要素と前の位置の要素を合計します。
5. ソート結果を格納するために、ソート対象の配列と同じ長さの一時配列を作成します。
6. ソート対象の配列を後ろから前にトラバースし、count 配列の累積値を使用して、一時配列内の対応する位置に要素を配置します。
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 中国語 Web サイトの他の関連記事を参照してください。