Comment effectuer un algorithme de tri et un algorithme de recherche en PHP ?

PHP, en tant que langage de programmation couramment utilisé, possède de nombreux algorithmes de tri et de recherche intégrés pour aider les développeurs à traiter plus efficacement de grandes quantités de données. Cet article présentera quelques algorithmes de tri et algorithmes de recherche courants et expliquera comment les utiliser en PHP.

1. Algorithme de tri

1. Tri à bulles

Le tri à bulles est un algorithme de tri de base. comparer les éléments adjacents par paires et échanger les positions en fonction de la relation de taille, atteignant ainsi l'objectif de tri. La méthode spécifique de mise en œuvre est la suivante :

function bubbleSort($arr) {
    $len = count($arr);

    for ($i = 0; $i < $len - 1; $i++) {
        for ($j = 0; $j < $len - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }

    return $arr;
}

2. Tri rapide

Le tri rapide est un algorithme de tri couramment utilisé. Son principe est de sélectionner un. valeur de référence, divisez le tableau à trier en deux parties plus petites que la valeur de référence et plus grandes que la valeur de référence, puis effectuez de manière récursive un tri rapide sur ces deux parties, et enfin fusionnez les résultats pour terminer le tri. La méthode spécifique d'implémentation est la suivante :

function quickSort($arr) {
    if (count($arr) < 2) {
        return $arr;
    }

    $pivot = $arr[0];
    $left = $right = [];

    for ($i = 1; $i < count($arr); $i++) {
        if ($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }

    return array_merge(quickSort($left), [$pivot], quickSort($right));
}

3. Tri par fusion

Le tri par fusion est un algorithme de tri classique Son principe est de trier le tableau. Continuez à diviser en sous-tableaux plus petits jusqu'à ce que chaque sous-tableau ne contienne qu'un seul élément, puis fusionnez les deux sous-tableaux adjacents et triez-les en fonction de la relation de taille, et répétez ce processus jusqu'à ce que le tableau entier soit trié. La méthode de mise en œuvre spécifique est la suivante :

function mergeSort($arr) {
    if (count($arr) < 2) {
        return $arr;
    }

    $mid = floor(count($arr) / 2);
    $left = array_slice($arr, 0, $mid);
    $right = array_slice($arr, $mid);

    return merge(mergeSort($left), mergeSort($right));
}

function merge($left, $right) {
    $result = [];

    while (count($left) && count($right)) {
        if ($left[0] <= $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }

    while (count($left)) {
        $result[] = array_shift($left);
    }

    while (count($right)) {
        $result[] = array_shift($right);
    }

    return $result;
}

2. Algorithme de recherche

1. Recherche séquentielle

La recherche séquentielle est aussi appelée recherche linéaire, son principe est de partir du premier élément du tableau à rechercher, et de comparer chaque élément un à un pour voir s'il est égal à la valeur cible, jusqu'à trouver la valeur cible ou la fin de la recherche. le tableau est recherché. La méthode spécifique de mise en œuvre est la suivante :

function linearSearch($arr, $target) {
    $len = count($arr);

    for ($i = 0; $i < $len; $i++) {
        if ($arr[$i] == $target) {
            return $i;
        }
    }

    return -1;
}

2. Recherche binaire

La recherche binaire est également appelée demi-recherche. Son principe est de cibler des tableaux ordonnés. La plage de recherche est continuellement réduite aux parties gauche et droite, et la valeur médiane du tableau est recherchée à chaque fois. Si la valeur médiane est supérieure à la valeur cible, la recherche se poursuit dans la moitié gauche, sinon la recherche se poursuit dans. la moitié droite jusqu'à ce que la valeur cible soit trouvée ou que la plage de recherche soit vide. La méthode d'implémentation spécifique est la suivante :

function binarySearch($arr, $target) {
    $low = 0;
    $high = count($arr) - 1;

    while ($low <= $high) {
        $mid = floor(($low + $high) / 2);
        if ($arr[$mid] < $target) {
            $low = $mid + 1;
        } else if ($arr[$mid] > $target) {
            $high = $mid - 1;
        } else {
            return $mid;
        }
    }

    return -1;
}

3. Résumé

Cet article présente les algorithmes de tri et les algorithmes de recherche courants, et fournit un exemple de code pour implémenter ces algorithmes en PHP. Bien que PHP dispose de nombreuses fonctions de tri et de recherche intégrées, la compréhension de ces algorithmes peut vous aider à approfondir votre compréhension des structures de données et des algorithmes et à améliorer vos compétences en programmation. Dans le même temps, dans le développement réel, nous pouvons choisir l'algorithme le plus approprié en fonction des besoins spécifiques pour améliorer l'efficacité et la qualité du code.

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!