PHP 配列のクイックソートとマージソート

クイック ソートは、配列を小さい要素と大きい要素に分割して再帰的に並べ替える再帰的アルゴリズムですが、マージ ソートは配列を小さい配列に再帰的に分割し、それぞれの小さい配列を並べ替えてから元の配列を返します。 PHP によって実装されるコードは次のとおりです。 クイック ソート: 配列をベースライン値より小さい要素と大きい要素に分割し、各部分を再帰的にソートします。マージソート: 配列を再帰的に小さな配列に分割し、それぞれの小さな配列をソートし、ソートされた小さな配列を元の配列にマージして戻します。

#PHP 配列のクイック ソートとマージ ソート

#クイック ソートとマージ ソートとは何ですか?

クイック ソートとマージ ソートはどちらも、配列のソートに使用される一般的なアルゴリズムです。

• クイック並べ替え: 配列を 2 つの部分に分割し、1 つは小さな要素を含み、もう 1 つは大きな要素を含み、各部分を再帰的に並べ替えます。
• マージソート: 配列を小さな配列に再帰的に分割し、それぞれの小さな配列をソートし、ソートされた小さな配列を元の配列にマージして戻します。

コードの実装

次に、PHP で実装されたクイック ソート関数とマージ ソート関数を示します:

クイック ソート:

function quickSort($arr) {
    if (count($arr) <= 1) {
        return $arr;
    }
    $pivot = $arr[0];
    $left = [];
    $right = [];
    for ($i = 1; $i < count($arr); $i++) {
        if ($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    return array_merge(quickSort($left), [$pivot], quickSort($right));
}

マージ ソート:

function mergeSort($arr) {
    $length = count($arr);
    if ($length <= 1) {
        return $arr;
    }
    $mid = floor($length / 2);
    $left = array_slice($arr, 0, $mid);
    $right = array_slice($arr, $mid);
    return merge(mergeSort($left), mergeSort($right));
}

function merge($left, $right) {
    $result = [];
    $lIndex = $rIndex = 0;
    while ($lIndex < count($left) && $rIndex < count($right)) {
        if ($left[$lIndex] < $right[$rIndex]) {
            $result[] = $left[$lIndex++];
        } else {
            $result[] = $right[$rIndex++];
        }
    }
    while ($lIndex < count($left)) {
        $result[] = $left[$lIndex++];
    }
    while ($rIndex < count($right)) {
        $result[] = $right[$rIndex++];
    }
    return $result;
}

実用的なケース

順序なし整数配列を検討してください

[5 , 2 、8、3、1、9、4、7、6].

クイックソートを使用する:

$sortedArray = quickSort([5, 2, 8, 3, 1, 9, 4, 7, 6]);
print_r($sortedArray);

出力:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

マージソートを使用する:

$sortedArray = mergeSort([5, 2, 8, 3, 1, 9, 4, 7, 6]);
print_r($sortedArray);

出力:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

以上がPHP 配列のクイックソートとマージソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。