So finden Sie den Median aus einem ungeordneten Array in PHP

In PHP ist Array eine sehr leistungsfähige Datenstruktur. Mit PHP-Arrays können wir große Datenmengen problemlos speichern und bearbeiten. Aber was machen wir, wenn wir den Median aus einem ungeordneten Array ermitteln müssen?

Der Median (auch Median genannt) ist der mittlere Wert in einem Array, der das Array in zwei Teile teilt, wobei alle Werte auf der linken Seite kleiner und alle Werte auf der rechten Seite größer sind. Wenn das Array eine gerade Anzahl von Elementen hat, ist der Median der Durchschnitt der beiden mittleren Elemente.

Obwohl PHP die Funktion sort() bereitstellt, die zum Sortieren großer Arrays verwendet werden kann, erreicht die Zeitkomplexität dieser Funktion O(nlogn) und ändert die Sortierreihenfolge des Arrays. Dies ist nicht Was wir wollen.

Wie finden wir also den Median eines ungeordneten Arrays in PHP, ohne die Reihenfolge des Arrays zu ändern? Schauen wir uns unten um.

1. Verwenden Sie die Schnellsortierung, um den Median zu ermitteln.

Der Schnellsortierungsalgorithmus ist ein vergleichsbasierter Sortieralgorithmus. Seine zeitliche Komplexität beträgt im Durchschnitt O(nlogn) und erfordert keinen zusätzlichen Speicherplatz. Daher können wir die Schnellsortierung verwenden, um das Array zu sortieren und den Median zu ermitteln.

Die Hauptidee des Schnellsortierungsalgorithmus besteht darin, ein Benchmark-Element im Array auszuwählen und das Array dann in zwei Teile zu teilen. Ein Teil enthält alle Werte, die kleiner als das Benchmark-Element sind, und der andere Teil enthält alle Werte, die kleiner als das Benchmark-Element sind enthält alle Werte, die größer als das Benchmark-Element sind. Diese beiden Teile werden dann rekursiv sortiert, bis das gesamte Array sortiert ist.

Um den Median eines ungeordneten Arrays zu finden, können wir es zuerst mit dem Schnellsortierungsalgorithmus sortieren und dann den Median basierend auf der Länge des sortierten Arrays bestimmen.

Das Folgende ist ein Beispiel für PHP-Code, der die Schnellsortierung verwendet, um die mittlere Zahl zu finden:

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;

2. Heap-Sortierung verwenden, um die mittlere Zahl zu finden

Der Heap-Sortieralgorithmus ist ein Sortieralgorithmus, der auf einem Heap-basierten Baum basiert Datenstruktur. Bei der Heap-Sortierung sortieren wir das Array, indem wir einen Max-Heap oder Min-Heap erstellen. Wir können Max Heap verwenden, um den Median eines ungeordneten Arrays zu ermitteln.

Max Heap ist ein Binärbaum, der die folgenden Eigenschaften erfüllt:

1 Der Wert jedes Knotens des Heaps ist größer oder gleich dem Wert seiner linken und rechten untergeordneten Knoten.

2. Der Heap ist immer ein vollständiger Binärbaum.

Für ein ungeordnetes Array können wir es sortieren, indem wir einen Max-Heap erstellen. Dann können wir den Median basierend auf den Eigenschaften des maximalen Heaps ermitteln.

Das Folgende ist ein Beispiel für PHP-Code, der Heap-Sortierung verwendet, um die mittlere Zahl zu finden:

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;

Zusammenfassung

Das Obige sind zwei Methoden, um die mittlere Zahl in einem ungeordneten Array in PHP zu finden. Obwohl ihre zeitliche Komplexität unterschiedlich ist, können sie alle die Funktionen zum schnellen Sortieren ungeordneter Arrays und zum Ermitteln des Medians implementieren. Wenn Sie eine große Anzahl ungeordneter Arrays sortieren und den Median ermitteln müssen, wird die Verwendung des Heap-Sortieralgorithmus empfohlen, der eine bessere Leistung bei der Zeitkomplexität bietet.

Das obige ist der detaillierte Inhalt vonSo finden Sie den Median aus einem ungeordneten Array in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!