PHP における基数ソート アルゴリズムの実装手順と時間計算量の分析。

PHP における基数ソート アルゴリズムの実装手順と時間計算量分析

基数ソートは、一般的に使用される線形時間計算量 (O(n )) ソート アルゴリズムであり、次の方法でソートを実現します。要素をビットごとに比較して割り当てます。この記事では、基数ソート アルゴリズムの実装手順を紹介し、その時間計算量を分析します。

基数ソートの基本的な考え方は、比較対象のすべての要素 (正の整数) を限られた数のバケットに割り当て、各バケット内の要素を順番に収集して最終的にソートを完了することです。

実装手順は次のとおりです:

1. バケット配列の初期化: バケットを表す 2 次元配列を作成します。各バケットは 1 次元配列です。バケットの数は、ソートする要素の最大桁数によって決まります。
2. 最大桁数を見つける: 並べ替える配列を走査し、最大の要素を見つけて、その桁数を決定します。
3. ビットごとに分散および収集します。下位ビットから上位ビットまで、各要素の対応する桁数の値を順番に取り出し、要素を対応するバケットに割り当てます。次に、それらをバケットの順序で元の配列に戻します。
4. ステップ 3: 最上位ビットが割り当てられるまで、順に上位ビットの割り当てと収集を繰り返します。
5. 完全なソート: 複数の割り当てとコレクションの後、ソート対象の配列が順序付けられました。

以下は基数ソートの PHP コードの例です:

function radixSort(array $arr): array {
    // 找到待排序数组的最大值
    $max = max($arr);
    
    // 确定最大值的位数
    $maxDigit = strlen((string)$max);
    
    // 初始化桶数组
    $buckets = [];
    for ($i = 0; $i < 10; $i++) {
        $buckets[$i] = [];
    }
    
    // 依次按位进行分配和收集
    for ($digit = 1; $digit <= $maxDigit; $digit++) {
        // 分配到桶中
        foreach ($arr as $num) {
            $index = ($num / pow(10, $digit - 1)) % 10;
            array_push($buckets[$index], $num);
        }
        
        // 按照桶的顺序进行收集
        $pos = 0;
        for ($i = 0; $i < 10; $i++) {
            while (!empty($buckets[$i])) {
                $arr[$pos] = array_shift($buckets[$i]);
                $pos++;
            }
        }
    }
    
    return $arr;
}

// 测试
$arr = [170, 45, 75, 90, 802, 24, 2, 66];
$result = radixSort($arr);
print_r($result);

時間計算量分析:

• If 要素の桁数をソート対象が d、バケットの数が k である場合、基数ソートの時間計算量は O(d * (n k)) です。
• 最悪の場合、ソート対象要素の桁数はバケット数と同じ、つまりd = kとなり、このときの時間計算量はO(2 * n)となります。
• 平均的な状況では、ソートされる要素の桁数はバケットの数に関係なく、つまり d

基数ソートは線形の時間計算量を実現できますが、空間の計算量は高く、要素を格納するには追加のバケット配列が必要です。さらに、負の数を扱う場合、要素に対する変換および反転演算も必要になります。ただし、実際のアプリケーションでは、並べ替えるデータが小さい場合、または環境に十分なメモリがある場合は、基数並べ替えが依然として効率的な並べ替えアルゴリズムです。

要約すると、この記事では、PHP での基数ソート アルゴリズムの実装手順を紹介し、その時間計算量を分析します。要素をビットごとに比較して割り当てることにより、基数ソートは並べ替えタスクを効率的に完了できます。実際のアプリケーションを作成する場合、ソートする要素の特性に基づいて適切なソート アルゴリズムを選択し、パフォーマンスを向上させることができます。

以上がPHP における基数ソート アルゴリズムの実装手順と時間計算量の分析。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。