PHPのクイックソートアルゴリズムの最適化戦略と実装方法は何ですか?-PHPチュートリアル-php.cn

PHPのクイックソートアルゴリズムの最適化戦略と実装方法は何ですか?

王林

リリース： 2023-09-19 11:16:01

オリジナル

936 人が閲覧しました

PHPのクイックソートアルゴリズムの最適化戦略と実装方法は何ですか?

PHP のクイックソートアルゴリズムの最適化戦略と実装方法は何ですか?

クイックソートは一般的な並べ替えアルゴリズムです。その基本的な考え方は、要素をベンチマーク値として選択し、配列を 2 つの部分に分割し、1 つの部分はベンチマーク値より小さく、もう 1 つの部分はベンチマーク値より大きいです。ベンチマーク値。次に、配列全体がソートされるまで、2 つの部分を別々にすばやくソートします。クイックソートを実装する場合、最適化戦略によってアルゴリズムのパフォーマンスを向上させることができます。

以下では、いくつかの最適化戦略と実装方法を紹介し、具体的な PHP コード例を示します。

ベンチマーク値をランダムに選択する
クイックソートでは、ベンチマーク値の選択がアルゴリズムのパフォーマンスに大きな影響を与えます。最初または最後の要素が毎回参照値として選択される場合、配列自体が順序付けされるか、またはほぼ順序付けされると、アルゴリズムの時間計算量は O(n^2) に達します。この状況を回避するには、基本値として要素をランダムに選択し、それによって最悪のシナリオが発生する確率を減らすことができます。

サンプルコード:

function partition($arr, $low, $high) {
    $pivot_index = rand($low, $high);
    // 交换基准值到数组最后一个位置
    $arr[$pivot_index] = $arr[$high];
    $arr[$high] = $arr[$pivot_index];
    
    $pivot = $arr[$high];
    $i = $low - 1;
    
    for ($j = $low; $j < $high; $j++) {
        if ($arr[$j] < $pivot) {
            $i++;
            // 交换元素位置
            $temp = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $temp;
        }
    }
    
    // 将基准值交换回正确的位置
    $temp = $arr[$i + 1];
    $arr[$i + 1] = $arr[$high];
    $arr[$high] = $temp;
    
    return $i + 1;
}

function quickSort($arr, $low, $high) {
    if ($low < $high) {
        $pivot_index = partition($arr, $low, $high);
        quickSort($arr, $low, $pivot_index - 1);
        quickSort($arr, $pivot_index + 1, $high);
    }
}

$arr = [5, 9, 3, 1, 6, 4, 8, 2, 7];
quickSort($arr, 0, count($arr) - 1);
echo implode(", ", $arr);  // 输出：1, 2, 3, 4, 5, 6, 7, 8, 9

ログイン後にコピー

3 数値法
ベンチマーク値を選択するとき、配列の最小値または最大値の選択を避けると、パフォーマンスを向上させることができます。アルゴリズム。基本値を取得する一般的な方法は、「3 数値法」を使用することです。つまり、配列の先頭、中間、および末尾から 3 つの要素を選択し、中央の値を基本値として取得します。

サンプルコード:

function getPivotIndex($arr, $low, $high) {
    $mid = intval(($low + $high) / 2);
    
    if ($arr[$low] < $arr[$mid]) {
        if ($arr[$mid] < $arr[$high]) {
            return $mid;
        } else if ($arr[$high] < $arr[$low]) {
            return $low;
        } else {
            return $high;
        }
    } else {
        if ($arr[$low] < $arr[$high]) {
            return $low;
        } else if ($arr[$mid] < $arr[$high]) {
            return $high;
        } else {
            return $mid;
        }
    }
}

function partition($arr, $low, $high) {
    $pivot_index = getPivotIndex($arr, $low, $high);
    // 交换基准值到数组最后一个位置
    $arr[$pivot_index] = $arr[$high];
    $arr[$high] = $arr[$pivot_index];
    
    $pivot = $arr[$high];
    $i = $low - 1;
    
    for ($j = $low; $j < $high; $j++) {
        if ($arr[$j] < $pivot) {
            $i++;
            // 交换元素位置
            $temp = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $temp;
        }
    }
    
    // 将基准值交换回正确的位置
    $temp = $arr[$i + 1];
    $arr[$i + 1] = $arr[$high];
    $arr[$high] = $temp;
    
    return $i + 1;
}

function quickSort($arr, $low, $high) {
    if ($low < $high) {
        $pivot_index = partition($arr, $low, $high);
        quickSort($arr, $low, $pivot_index - 1);
        quickSort($arr, $pivot_index + 1, $high);
    }
}

$arr = [5, 9, 3, 1, 6, 4, 8, 2, 7];
quickSort($arr, 0, count($arr) - 1);
echo implode(", ", $arr);  // 输出：1, 2, 3, 4, 5, 6, 7, 8, 9

ログイン後にコピー

ベンチマーク値をランダムに選択したり、3 つの数値の中央を取るなどの最適化戦略を採用することで、クイックソートアルゴリズムのパフォーマンスを向上させることができます。最悪のシナリオを減らすことができます。これらの最適化戦略は、大規模なデータセットの並べ替えに適用される場合、アルゴリズムの効率を向上させるために特に重要です。

以上がPHPのクイックソートアルゴリズムの最適化戦略と実装方法は何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。