PHPを使用して逆順アルゴリズムを実装する方法

PHP を使用して逆順ペア アルゴリズムを実装する方法

コンピュータ サイエンスでは、逆順ペアはシーケンス内にあります。任意の 2 つの要素 ai と aj について、i aj, 逆順ペアといいます。逆順序問題を解くことは実用上非常に重要であり、並べ替え問題の最適化やデータ分析などの分野に応用されています。

この記事では、この一般的な問題をより深く理解し、習得するために、PHP プログラミング言語を使用して逆ペア アルゴリズムを実装する方法を紹介します。

まず、逆順ペアを計算する方法を考える必要があります。簡単なアプローチは、2 つのネストされたループを使用し、要素のすべてのペアを毎回比較することです。条件ａｉ＞ａｊが満たされる場合、逆順序ペアのカウンタをインクリメントする。ただし、この方法の時間計算量は O(n^2) であり、大規模なデータ セットには適していません。

もう 1 つのより効率的な方法は、マージ ソート アルゴリズムを使用することです。このアルゴリズムの基本的な考え方は、シーケンスをより小さなサブシーケンスに分解し、それらをより大きなソートされたシーケンスにマージすることです。マージプロセス中に、ペアの数を逆順に簡単に数えることができます。

以下は、PHP プログラミング言語を使用して逆順アルゴリズムを実装するためのコード例です。

function mergeSortCount(&$arr) {
    $temp = array();
    $count = 0;
    $length = count($arr);
    $temp = array_fill(0, $length, 0); // 创建一个临时数组用于存储合并过程中的结果

    $count = mergeSort($arr, $temp, 0, $length - 1); // 调用真正的归并排序函数

    return $count;
}

function mergeSort(&$arr, &$temp, $left, $right) {
    $count = 0;
    if ($left < $right) {
        $mid = floor(($left + $right) / 2); // 找到中间位置
        $count += mergeSort($arr, $temp, $left, $mid); // 递归地对左子数组进行排序
        $count += mergeSort($arr, $temp, $mid + 1, $right); // 递归地对右子数组进行排序
        $count += merge($arr, $temp, $left, $mid + 1, $right); // 合并左右子数组，并计算逆序对数量
    }
    return $count;
}

function merge(&$arr, &$temp, $left, $mid, $right) {
    $count = 0;
    $i = $left; // 左子数组起始位置
    $j = $mid; // 右子数组起始位置
    $k = $left; // 合并后的数组起始位置

    while ($i <= $mid - 1 && $j <= $right) {
        if ($arr[$i] <= $arr[$j]) {
            $temp[$k++] = $arr[$i++];
        } else {
            $temp[$k++] = $arr[$j++];
            $count += $mid - $i;
        }
    }

    while ($i <= $mid - 1) {
        $temp[$k++] = $arr[$i++];
    }

    while ($j <= $right) {
        $temp[$k++] = $arr[$j++];
    }

    for ($i = $left; $i <= $right; $i++) {
        $arr[$i] = $temp[$i];
    }

    return $count;
}

// 测试示例
$arr = array(3, 1, 2, 4, 5);
$count = mergeSortCount($arr);
echo "逆序对的数量：" . $count;

上記のコードは、まず mergeSortCount 関数を定義します。配列をパラメータとして受け取り、ペアの数を逆順に返します。この関数では、一時配列 temp を作成し、カウンター count を初期化し、配列の長さ length を記録します。

次に、mergeSort 関数を呼び出して、実際のマージ ソートを実行します。 mergeSort この関数は、左閉区間 $left と右閉区間 $right をパラメータとして受け取ります。各再帰呼び出しでは、配列を分割して再帰します。部分配列を並べ替えてから、merge 関数を呼び出して部分配列をマージし、逆のペアの数を数えます。

merge 関数では、左側に 3 つのポインター $i、$j、$k を使用します。 、右側の部分配列とマージされた配列が走査されます。左の部分配列の現在の要素が右の部分配列の現在の要素以下の場合、左の部分配列の現在の要素を一時配列に入れ、$i と $k ポインタが 1 つ後ろに移動します。右のサブ配列の現在の要素が左のサブ配列の現在の要素より小さい場合は、右のサブ配列の現在の要素を一時配列に入れ、$j と $k を移動します。ポインタを後方に移動します。 位置を 1 つ移動します。このプロセスでは、右のサブ配列の現在の要素が左のサブ配列の現在の要素より小さい場合、カウンタ $count が、左のサブ配列の現在位置から最後の部分までの要素の数に追加されます。中央の位置 (左側のサブ配列がすでに順序付けられているため)。

最後に、一時配列 $temp の要素を元の配列 $arr にコピーし、カウンター $count## を返します。 ＃。

最後のテスト例では、5 つの整数を含む配列を定義し、

mergeSortCount 関数を呼び出して逆順ペアの数を数えました。この例では、反転ペアの数は 2 です。

上記のコード例を通して、PHP プログラミング言語を使用して逆ペア アルゴリズムを実装するのは難しくないことがわかります。マージ ソート アルゴリズムの中心となるアイデアは、シーケンスをより小さなサブシーケンスに分解し、マージ操作によるソートを実装し、同時に逆順ペアの数を計算することです。これは、さまざまな実際的な問題に適用できる、効率的で一般的に使用される並べ替えアルゴリズムです。

以上がPHPを使用して逆順アルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。