Implémentation de l'algorithme PHP Comb Sort

Le tri en peigne ou tri en peigne est une variante du Tri à bulles . Semblable au Shell Sort, Comb Sort augmente les écarts utilisés dans les comparaisons et les échanges. Certaines implémentations utilisent le tri par insertion lorsque l'intervalle est inférieur à un certain nombre. L'idée de base est d'éliminer les petites valeurs vers la fin de la liste, car dans le tri à bulles, elles ralentiront considérablement le tri. Et les valeurs élevées au début de la liste ne poseront pas de problèmes de tri à bulles.

Dans le tri à bulles, lorsque deux éléments sont comparés, ils ont toujours un écart de 1. L'idée de base du tri au peigne est que l'écart peut être bien supérieur à 1.

Le diagramme de tri des peignes PHP est le suivant :

L'exemple de code est le suivant :

<?php
function combSort($my_array){
    $gap = count($my_array);
    $swap = true;
    while ($gap > 1 || $swap){
        if($gap > 1) $gap /= 1.25;
        $swap = false;
        $i = 0;
        while($i+$gap < count($my_array)){
            if($my_array[$i] > $my_array[$i+$gap]){
                list($my_array[$i], $my_array[$i+$gap]) = array($my_array[$i+$gap],$my_array[$i]);
                $swap = true;
            }
            $i++;
        }
    }
    return $my_array;
}
$test_array = array(3, 0, 2, 5, -1, 4, 1);
echo "原始数组 :\n";
echo implode(&#39;, &#39;,$test_array );
echo "\n排序后数组\n:";
echo implode(&#39;, &#39;,combSort($test_array)). PHP_EOL;

Sortie :

原始数组 : 3, 0, 2, 5, -1, 4, 1
排序后数组 :-1, 0, 1, 2, 3, 4, 5

Cet article concerne la méthode d'implémentation de l'algorithme PHP Comb Sort. J'espère qu'il sera utile aux amis dans le besoin !

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!