Introduction aux algorithmes de bullage, d'insertion binaire et de tri rapide-tutoriel php-php.cn

Introduction aux algorithmes de bullage, d'insertion binaire et de tri rapide

jacklove

Libérer： 2023-03-31 12:28:01

original

2175 Les gens l'ont consulté

1. Algorithme de tri des bulles
Processus :
1. Parcourez l'ensemble du tableau et comparez chaque paire d'éléments adjacents, tels que $ a[. $i]>$a[$i+1] échange les positions et chaque comparaison élimine un ordre inverse.
2. Après chaque cycle, le nombre de cycles requis la prochaine fois est réduit de 1.

<?php
// 冒泡排序
$arr = createarr(20);
printarr($arr);
popsort($arr);
printarr($arr);
function createarr($num=10){
    $arr = array();
    for($i=0; $i<$num; $i++){
        array_push($arr, mt_rand(0,999));
    }
    return $arr;
}
function printarr($arr){
    echo &#39;arr:&#39;.implode(&#39;,&#39;, $arr).&#39;<br>&#39;;
}
function popsort(&$arr){
    for($i=0,$length=count($arr)-1; $i<$length; $i++){
        for($j=0; $j<$length-$i; $j++){
            if($arr[$j]>$arr[$j+1]){
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $tmp;
            }
        }
    }    
}
?>

Copier après la connexion

2. Tri par insertion binaire

Processus :
1 . Premièrement, le tableau d'origine est une séquence ordonnée, $low=0 $high=count($arr)-1.
2. Comparez le nombre à insérer avec l'élément au milieu du tableau
S'il est plus grand que l'élément du milieu, $low=$mid+1 sera utilisé comme début du tableau pour. le prochain jugement.
S'il est plus petit que l'élément du milieu, $high=$mid-1 sera utilisé comme fin du tableau pour le prochain jugement.
3. Jusqu'à la fin de $low>$high, $low est la position où le nouvel élément est inséré.
4. Déplacez tous les éléments à partir de $low dans le tableau vers l'arrière d'un point, puis insérez de nouveaux éléments à la position $low.

<?php
// 二分法插入排序
$arr = createarr(20);
$key = mt_rand(0,99);
printarr($arr);
echo &#39;key=&#39;.$key.&#39;<br>&#39;;
binsort($arr, $key);
printarr($arr);
function createarr($num=10){
    $arr = array();
    for($i=0; $i<$num; $i++){
        array_push($arr, mt_rand(0,99));
    }
    sort($arr); // 有序序列
    return $arr;
}
function printarr($arr){
    echo &#39;arr:&#39;.implode(&#39;,&#39;, $arr).&#39;<br>&#39;;
}
function binsort(&$arr, $key){
    $low = 0;
    $high = count($arr)-1;
    while($low<=$high){
        $m = $low + (int)(($high-$low)/2);
        $mkey = $arr[$m];
        if($key>=$mkey){
            $low = $m + 1;
        }else{
            $high = $m - 1;
        }
    }
    // 移动插入位置之后的元素,插入新元素
    for($i=count($arr)-1; $i>=$low; $i--){
        $arr[$i+1] = $arr[$i];
    }
    $arr[$low] = $key;
}
?>

Copier après la connexion

3. Tri rapide
Processus :
1. Trouver un élément dans le tableau comme clé, Généralement, le premier élément du tableau est considéré comme la clé
2, j=array length-1
3 j-- lorsque arr[j]4. i++ Lorsque arr[i]>key, arr[i] et arr[j] échangent les positions
5. Répétez 3,4 jusqu'à ce que i==j, terminez.
6. Exécutez 1, 2, 3, 4, 5 (récursivement) sur les ensembles d'éléments gauche et droit séparés par clé.

<?php
// 快速排序
$arr = createarr(20);
printarr($arr);
quicksort($arr, 0, count($arr)-1);
printarr($arr);
function createarr($num=10){
    $arr = array();
    for($i=0; $i<$num; $i++){
        array_push($arr, mt_rand(0,999));
    }
    return $arr;
}
function printarr($arr){
    echo &#39;arr:&#39;.implode(&#39;,&#39;, $arr).&#39;<br>&#39;;
}
function quicksort(&$arr, $low, $high){
    if($low>=$high){
        return ;
    }
    $key = $arr[$low];
    $i = $low;
    $j = $high;
    $flag = 1;
    while($i!=$j){
        switch($flag){
            case 0:
                if($arr[$i]>$key){
                    $tmp = $arr[$i];
                    $arr[$i] = $arr[$j];
                    $arr[$j] = $tmp;
                    $flag = 1;
                }else{
                    $i++;
                }
                break;
            case 1:
                if($arr[$j]<$key){
                    $tmp = $arr[$i];
                    $arr[$i] = $arr[$j];
                    $arr[$j] = $tmp;
                    $flag = 0;
                }else{
                    $j--;
                }
                break;
        }
    }
    quicksort($arr, $low, $i-1);
    quicksort($arr, $i+1, $high);
}
?>

Copier après la connexion

Cet article explique les algorithmes de bouillonnement, d'insertion dichotomique et de tri rapide. Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois.

Recommandations associées :

Comment filtrer les classes d'attributs de balises HTML via PHP

Comment utiliser PHP pour remplacer les opérations liées aux chaînes sensibles

À propos de PHP traversant des dossiers, des classes de fichiers et des classes de traitement

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!