PHPで順序なし配列から中央値を見つける方法

PHP では、配列は非常に強力なデータ構造です。 PHP 配列を使用すると、大量のデータを簡単に保存および操作できます。しかし、順序のない配列から中央値を見つける必要がある場合はどうすればよいでしょうか?

中央値 (中央値とも呼ばれます) は配列内の中央の値です。配列を 2 つの部分に分割します。左側のすべての値はそれより小さく、右側のすべての値は大きめです。配列の要素数が偶数の場合、中央値は中央の 2 つの要素の平均になります。

PHP には、配列の並べ替えに使用できる sort() 関数が用意されていますが、大きな配列を並べ替える場合、この関数の時間計算量は O(nlogn) に達し、配列の並べ替えが変更されます。命令、これは私たちが望んでいることではありません。

それでは、配列の順序を変更せずに、PHP で順序なし配列の中央値を見つけるにはどうすればよいでしょうか?以下を見てみましょう。

1. クイック ソートを使用して中央値を見つける

クイック ソート アルゴリズムは比較ベースの並べ替えアルゴリズムであり、平均的な状況下での時間計算量は O(nlogn) です。追加のメモリ領域は必要ありません。したがって、クイック ソートを使用して配列を並べ替え、中央値を見つけることができます。

クイック ソート アルゴリズムの主なアイデアは、配列内のベンチマーク要素を選択し、配列を 2 つの部分に分割することです。1 つの部分には、ベンチマーク要素よりも小さいすべての値が含まれます。他の部分には、ベンチマーク要素よりも大きいすべての値が含まれます。これら 2 つの部分は、配列全体がソートされるまで再帰的にソートされます。

順序なし配列の中央値を見つけるには、クイック ソート アルゴリズムを使用してまず配列を並べ替え、次に並べ替えられた配列の長さに基づいて中央値を決定します。

次は、クイック ソートを使用して中間の数値を検索する PHP コードの例です。

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

$arr = array(3, 9, 2, 7, 1, 5, 6);
$sorted_arr = quickSort($arr);
$len = count($sorted_arr);
if($len % 2 == 0){
    $middle = ($sorted_arr[$len/2-1] + $sorted_arr[$len/2])/2;
}else{
    $middle = $sorted_arr[($len-1)/2];
}
echo "中数为：".$middle;

#ヒープ ソートを使用して中間の数値を検索します
#ヒープソートアルゴリズムは、ヒープベースのツリーデータ構造のソートアルゴリズムです。ヒープソートでは、最大ヒープまたは最小ヒープを構築して配列をソートします。最大ヒープを使用して、順序なし配列の中央値を見つけることができます。

最大ヒープは、次のプロパティを満たすバイナリ ツリーです:

1. ヒープの各ノードの値は、その左右の子ノードの値以上です。

2. ヒープは常に完全なバイナリ ツリーです。

順序なし配列の場合、最大ヒープを構築することで配列を並べ替えることができます。次に、最大ヒープの特性に基づいて中央値を見つけることができます。

以下は、ヒープ ソートを使用して中央値を検索する PHP コードの例です。

function buildMaxHeap(&$arr, $index, $heapSize){
    $left = 2*$index+1;
    $right = 2*$index+2;
    $max = $index;
    if($left<$heapSize && $arr[$left]>$arr[$max]){
        $max = $left;
    }
    if($right<$heapSize && $arr[$right]>$arr[$max]){
        $max = $right;
    }
    if($max != $index){
        $temp = $arr[$index];
        $arr[$index] = $arr[$max];
        $arr[$max] = $temp;
        buildMaxHeap($arr, $max, $heapSize);
    }
}

function heapSort(&$arr){
    $heapSize = count($arr);
    for($i=intval($heapSize/2)-1; $i>=0; $i--){
        buildMaxHeap($arr, $i, $heapSize);
    }
    for($i=$heapSize-1; $i>=1; $i--){
        $temp = $arr[0];
        $arr[0] = $arr[$i];
        $arr[$i] = $temp;
        $heapSize--;
        buildMaxHeap($arr, 0, $heapSize);
    }
}

$arr = array(3, 9, 2, 7, 1, 5, 6);
heapSort($arr);
$len = count($arr);
if($len % 2 == 0){
    $middle = ($arr[$len/2-1] + $arr[$len/2])/2;
}else{
    $middle = $arr[($len-1)/2];
}
echo "中数为：".$middle;

概要

上記は、順序なし配列で中央値を検索する 2 つの方法です。 PHPで。時間計算量は異なりますが、順序付けされていない配列を迅速にソートし、中央値を見つける機能はすべて実装できます。多数の順序なし配列を並べ替えて中央値を見つける必要がある場合は、時間計算量のパフォーマンスが優れているヒープ ソート アルゴリズムを使用することをお勧めします。

以上がPHPで順序なし配列から中央値を見つける方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。