Implémentation de l'algorithme de tri PHP Hill (Shell) (explication détaillée du code)

Le tri Hill (Shell) ou méthode Shell est un tri par comparaison sur place. Cela peut être vu comme une généralisation du tri à bulles ou du tri par insertion. Cette méthode trie d’abord les paires d’éléments éloignés les uns des autres, puis réduit progressivement l’écart entre les éléments à comparer. Commencer par des éléments éloignés les uns des autres vous permet de déplacer certains éléments déplacés plus rapidement que l'échange de voisins.

L'exemple de tri de shell est le suivant :

Le premier parcours est "5 tri " , effectuez un tri par insertion sur différents sous-tableaux (a1, a6, a11), (a2, a7, a12), (a3, a8), (a4, a9), (a5, a10). Par exemple, cela modifie le sous-tableau (a1, a6, a11) de (62,17,25) à (17,25,62).

Puis "3 tri", effectuez un tri par insertion sur les sous-tableaux (a1, a4, a7, a10), (a2, a5, a8, a11), (a3, a6, a9, a12).

La dernière fois est "1 tri", qui correspond à l'ensemble du tableau (a1,...,a12). Comme le montre l'exemple, les sous-tableaux des opérations de tri Shell sont initialement très courts ; puis ils deviennent plus longs, mais ils sont fondamentalement ordonnés. Dans les deux cas, le tri par insertion fonctionne. Le tri du shell est instable : il peut modifier l'ordre relatif des éléments de valeurs égales. Il s'agit d'un algorithme de tri adaptatif qui s'exécute plus rapidement lorsque l'entrée est partiellement triée.

Le graphique de tri Hill (Shell) est le suivant :

Exemple de code de PHP implémentant l'algorithme de tri Shell (Shell) :

<?php
function shell_Sort($my_array)
{
    $x = round(count($my_array)/2);
    while($x > 0)
    {
        for($i = $x; $i < count($my_array);$i++){
            $temp = $my_array[$i];
            $j = $i;
            while($j >= $x && $my_array[$j-$x] > $temp)
            {
                $my_array[$j] = $my_array[$j - $x];
                $j -= $x;
            }
            $my_array[$j] = $temp;
        }
        $x = round($x/2.2);
    }
    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;,shell_Sort($test_array)). PHP_EOL;

Sortie :

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

Cet article est une introduction à l'algorithme de tri PHP Hill (Shell). Il est simple et facile à comprendre. 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!