PHP implémente plusieurs algorithmes de tri et de recherche-tutoriel php-php.cn

PHP implémente plusieurs algorithmes de tri et de recherche

little bottle

Libérer： 2023-04-05 22:52:01

avant

1811 Les gens l'ont consulté

Le tri à bulles, le tri rapide et la recherche binaire sont simples, mais ils sont faciles à oublier si vous ne les utilisez pas pendant un certain temps. Voici le code d'implémentation PHP que l'éditeur a trouvé et partagé avec tout le monde pour apprendre ensemble.

Trier

Tri à bulles

La plus grande valeur apparaît à chaque fois

function bubbleSort($arr)
{
    $count = count($arr);
    if ($count == 0) return false;

    for ($i = 0; $i < $count - 1; $i++) {
        for ($k = 0; $k < $count - 1 - $i; $k++) {
            if ($arr[$k] < $arr[$k + 1]) {
                $tmp         = $arr[$k];
                $arr[$k]     = $arr[$k + 1];
                $arr[$k + 1] = $tmp;
            }
        }
    }

    return $arr;
}

Copier après la connexion

Tri rapide

Sélectionner une valeur en tant que benchmark, les plus petits sont placés à gauche, les plus grands sont placés à droite, puis la gauche et la droite sont récursées, et enfin fusionnées

function quickSort($arr)
{
    $count = count($arr);
    if ($count <= 1) return $arr;

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

    $left  = quickSort($left);
    $right = quickSort($right);

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

Copier après la connexion

Tri par sélection

Sélectionner une valeur supposée être la plus petite, Puis comparez-les une à une, et si vous trouvez qu'elle est plus petite que lui, échangez les positions

function selectSort($arr)
{
    $count = count($arr);
    if ($count <= 1) return $arr;

    for ($i = 0; $i < $count; $i++) {
        //假设最小值位置
        $p = $i;
        //用假设的最小值$arr[$p]轮流比较，发现比他小的就互换
        for ($j = $i + 1; $j < $count; $j++) {
            if ($arr[$p] > $arr[$j]) {
                $p = $j;
            }
        }

        if ($p != $i) {
            $tmp     = $arr[$p];
            $arr[$p] = $arr[$i];
            $arr[$i] = $tmp;
        }
    }

    return $arr;
}

Copier après la connexion

Recherche

Recherche binaire

La recherche binaire doit être un tableau trié, chaque fois que vous obtenez Comparez la valeur en position médiane du tableau avec la cible

function binarySearch(array $arr, $target)
{
    $low = 0;
    $high = count($arr) - 1;
    while ($low <= $high) {
        $middle = floor(($high + $low) / 2);
        if ( $arr[$middle] == $target ) {
            return $middle;
        } elseif ( $arr[$middle] < $target ) {
            $low = $middle + 1;
        } else {
            $high = $middle - 1;
        }
    }

    return false;
}

Copier après la connexion

Tutoriel recommandé : Tutoriel vidéo PHP

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!