Comment trouver la médiane d'un tableau non ordonné en php

En PHP, un tableau est une structure de données très puissante. Avec les tableaux PHP, nous pouvons facilement stocker et manipuler de grandes quantités de données. Mais que faire lorsque nous devons trouver la médiane d’un tableau non ordonné ?

La médiane (également appelée médiane) est la valeur médiane d'un tableau, qui divise le tableau en deux parties, toutes les valeurs de gauche étant plus petites qu'elle et toutes les valeurs de droite étant plus grandes. Si le tableau comporte un nombre pair d’éléments, la médiane est la moyenne des deux éléments du milieu.

Bien que PHP fournisse la fonction sort(), qui peut être utilisée pour trier des tableaux, lors du tri de grands tableaux, la complexité temporelle de cette fonction atteindra O(nlogn) et modifiera l'ordre de tri du tableau. Ce n'est pas quoi. nous voulons.

Alors, comment trouver la médiane d'un tableau non ordonné en PHP sans changer l'ordre du tableau ? Jetons un coup d'œil ci-dessous.

1. Utilisez le tri rapide pour trouver la médiane

L'algorithme de tri rapide est un algorithme de tri basé sur la comparaison. Sa complexité temporelle est en moyenne de O(nlogn) et ne nécessite pas d'espace mémoire supplémentaire. Par conséquent, nous pouvons utiliser le tri rapide pour trier le tableau et trouver la médiane.

L'idée principale de l'algorithme de tri rapide est de sélectionner un élément de référence dans le tableau, puis de diviser le tableau en deux parties, une partie contient toutes les valeurs qui sont plus petites que l'élément de référence et l'autre partie contient toutes les valeurs supérieures à l'élément de référence. Ces deux parties sont ensuite triées de manière récursive jusqu'à ce que l'ensemble du tableau soit trié.

Afin de trouver la médiane d'un tableau non ordonné, nous pouvons d'abord le trier à l'aide de l'algorithme de tri rapide, puis déterminer la médiane en fonction de la longueur du tableau trié.

Ce qui suit est un exemple de code PHP qui utilise le tri rapide pour trouver le nombre du milieu :

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. Utiliser le tri par tas pour trouver le nombre du milieu

L'algorithme de tri par tas est un algorithme de tri basé sur un arbre basé sur des tas structure des données. Dans le tri par tas, nous trions le tableau en construisant un tas maximum ou un tas min. Nous pouvons utiliser max tas pour trouver la médiane d’un tableau non ordonné.

Max tas est un arbre binaire qui satisfait les propriétés suivantes :

1. La valeur de chaque nœud du tas est supérieure ou égale à la valeur de ses nœuds enfants gauche et droit.

2. Le tas est toujours un arbre binaire complet.

Pour un tableau non ordonné, nous pouvons le trier en construisant un tas maximum. Ensuite, nous pouvons trouver la médiane en fonction des propriétés du tas maximum.

Ce qui suit est un exemple de code PHP qui utilise le tri par tas pour trouver le nombre du milieu :

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;

Résumé

Ci-dessus sont deux méthodes pour trouver le nombre du milieu dans un tableau non ordonné en PHP. Bien que leur complexité temporelle soit différente, ils peuvent tous implémenter les fonctions de tri rapide des tableaux non ordonnés et de recherche de la médiane. Si vous devez trier un grand nombre de tableaux non ordonnés et trouver la médiane, il est recommandé d'utiliser l'algorithme de tri par tas, qui offre de meilleures performances en termes de complexité temporelle.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!