Analyse complète de l'algorithme de tri de tableau PHP: comment rédiger des fonctions de tri personnalisées

Analyse complète de l'algorithme de tri de tableau PHP

Le tri du tableau est une tâche très courante dans la programmation, et il nous aide à réorganiser les éléments dans un tableau en fonction des règles spécifiées. En PHP, plusieurs fonctions de tri sont intégrées, mais dans certains cas, nous devrons peut-être écrire nos propres algorithmes de tri pour répondre aux besoins spécifiques. Cet article se concentrera sur la façon de personnaliser l'algorithme de tri de tableau PHP, y compris le tri de bulles commun, le tri de sélection et les algorithmes de tri insérés, et fournir des exemples de code pratiques.

Tri bulle

Le tri des bulles est un algorithme de tri simple qui compare à plusieurs reprises des éléments adjacents et échange leurs positions jusqu'à ce que le tableau entier soit ordonné. Sa complexité temporelle est O (n²), qui est plus adaptée à l'utilisation lorsque le volume de données est faible.

 function bubbleSort(array &$arr) {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $tmp;
            }
        }
    }
}

Sélectionner le tri

L'idée de base de choisir le tri est de sélectionner le plus petit (ou le plus grand) élément de la partie non triée et de le mettre à la fin de la partie triée. Il est légèrement plus optimisé que le tri des bulles, mais la complexité du temps est toujours O (n²), adaptée au tri de données à petite échelle.

 function selectionSort(array &$arr) {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        $min_idx = $i;
        for ($j = $i + 1; $j < $n; $j++) {
            if ($arr[$j] < $arr[$min_idx]) {
                $min_idx = $j;
            }
        }
        $tmp = $arr[$i];
        $arr[$i] = $arr[$min_idx];
        $arr[$min_idx] = $tmp;
    }
}

Insérer le tri

Le tri d'insertion est un moyen d'insérer chaque nouvel élément dans la partie déjà triée pour former un nouveau tableau ordonné. Sa complexité temporelle est O (n²), mais elle est plus efficace lorsque le volume de données est faible et est souvent utilisé pour le tri des données à petite échelle.

 function insertionSort(array &$arr) {
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        $arr[$j + 1] = $key;
    }
}

Cas pratiques

Ensuite, nous allons trier un tableau PHP dans l'ordre croissant en utilisant l'algorithme de tri de bulles:

 $arr = [5, 2, 8, 3, 1];
bubbleSort($arr);

Le tableau trié est le suivant:

 [1, 2, 3, 5, 8]

Résumer

Cet article présente trois algorithmes de tri de tableau PHP communs: tri de bulles, tri de sélection et tri inséré. Bien que ces méthodes de tri soient simples, elles peuvent nous aider à maîtriser les idées d'algorithmes de tri de base. Dans le développement réel, nous pouvons choisir la méthode de tri appropriée en fonction des besoins spécifiques. Pour un tri plus efficace, vous pouvez considérer les fonctions de tri intégrées PHP telles que Sort () et USORT () .