PHP の配列ソートと検索アルゴリズム

PHP は、さまざまなデータ型とアルゴリズムをサポートする非常に人気のあるプログラミング言語であり、配列の並べ替えと検索アルゴリズムは基本的かつ重要な部分です。この記事では、PHP で一般的に使用される配列の並べ替えと検索アルゴリズム、およびそのアプリケーション シナリオと効率分析を紹介します。

1. 配列ソート

PHP は、バブル ソート、挿入ソート、選択ソート、クイック ソート、マージ ソートなどを含む、さまざまな配列ソート方法を提供します。以下は、一般的に使用されるいくつかのアルゴリズムの紹介とサンプル コードです:

1. バブル ソート

バブル ソートはシンプルですが非効率です ソート アルゴリズムの基本的な考え方配列の最初の要素から順に隣り合う要素の大きさを比較し、左の要素が右の要素より大きい場合、位置を入れ替えます。このラウンドの比較の後、最大の要素が配列の最後に移動されます。次に、最初の要素から開始して上記の操作を繰り返すと、時間計算量は O(n^2) になります。

サンプル コード:

function bubble_sort($arr) {
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        for ($j = 0; $j < $len - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
    return $arr;
}

2. 挿入ソート

挿入ソートは、比較的単純な並べ替えアルゴリズムです。その基本的な考え方は、並べ替えられるデータは次のとおりです。ソートの目的を達成するために、すでにソート済みのシーケンスに挿入されます。前の要素がソートされていると仮定して、配列の 2 番目の要素から開始して、挿入操作に適した位置を探します。バブルソートと同様に、その時間計算量も O(n^2) です。

サンプル コード:

function insertion_sort($arr) {
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $temp = $arr[$i];
        for ($j = $i - 1; $j >= 0 && $arr[$j] > $temp; $j--) {
            $arr[$j + 1] = $arr[$j];
        }
        $arr[$j + 1] = $temp;
    }
    return $arr;
}

3. クイック ソート

クイック ソートは、一般的に使用される効率的な並べ替えアルゴリズムです。その基本的な考え方は、配列が基本値として使用され、残りの要素が 2 つのサブシーケンスに分割されます。左側の数値はすべて基本値より小さく、右側の数値はすべて基本値より大きくなります。次に、サブシーケンスの長さが 1 または 0 になるまで、左と右のサブシーケンスに対して上記の手順を繰り返します。クイックソートの計算量は O(n log2 n) であり、不安定なソートです。

サンプルコード:

function quick_sort($arr) {
    $len = count($arr);
    if ($len <= 1) {
        return $arr;
    }
    $pivot_key = $arr[0];
    $left_arr = array();
    $right_arr = array();
    for ($i = 1; $i < $len; $i++) {
        if ($arr[$i] <= $pivot_key) {
            $left_arr[] = $arr[$i];
        } else {
            $right_arr[] = $arr[$i];
        }
    }
    $left_arr = quick_sort($left_arr);
    $right_arr = quick_sort($right_arr);
    return array_merge($left_arr, array($pivot_key), $right_arr);
}

2. 配列検索

PHP の配列検索アルゴリズムには、主に線形検索、二分検索、ハッシュ検索があります。

1. 線形検索

線形検索は単純な検索アルゴリズムです。基本的な考え方は、配列の最初の要素を取得し、要素の値とキーワードを 1 つずつ比較して同じかどうかを確認し、存在する場合は要素の添字を返し、存在しない場合は -1 を返します。線形探索の時間計算量は O(n) です。

サンプルコード:

function linear_search($arr, $key) {
    $len = count($arr);
    for ($i = 0; $i < $len; $i++) {
        if ($arr[$i] == $key) {
            return $i;
        }
    }
    return -1;
}

2. 二分探索

二分探索は半探索とも呼ばれ、基本的な考え方は、順序付けられた配列を 2 つに分割することです。部分はその都度中間要素とキーワードの大きさを比較し、等しければその要素の添え字を返し、等しくない場合は目的の要素が見つかるまで大小関係に従って検索範囲を半分に縮小します。二分探索の時間計算量は O(log2 n) です。

サンプル コード:

function binary_search($arr, $key) {
    $low = 0;
    $high = count($arr) - 1;
    while ($low <= $high) {
        $mid = floor(($low + $high) / 2);
        if ($arr[$mid] == $key) {
            return $mid;
        } elseif ($arr[$mid] > $key) {
            $high = $mid - 1;
        } else {
            $low = $mid + 1;
        }
    }
    return -1;
}

3. ハッシュ検索

ハッシュ検索は、ハッシュ テーブルを使用した効率的な検索アルゴリズムです。基本的な考え方は、各要素のキーをハッシュ テーブルにマッピングし、ハッシュ関数を通じてその位置を計算し、その位置で必要な要素を見つけることです。ハッシュ検索の時間計算量は O(1) ですが、ハッシュ テーブルを構築して維持する必要があります。

上記は、PHP で一般的に使用される配列ソートおよび検索アルゴリズムの紹介とサンプル コードです。実際のアプリケーション シナリオやデータ サイズに応じて異なるアルゴリズムを選択すると、コードの効率が向上します。

以上がPHP の配列ソートと検索アルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。