Une explication de la façon d'implémenter l'algorithme de tri Hill en PHP

Cet article présente principalement la méthode d'implémentation de l'algorithme de tri Hill en PHP, explique brièvement le principe du tri Hill et analyse les compétences opérationnelles spécifiques de PHP implémentant le tri Hill sous forme d'exemples. Les amis dans le besoin peuvent s'y référer<.>

L'exemple de cet article décrit comment implémenter l'algorithme de tri Hill en PHP. Partagez-le avec tout le monde pour votre référence, comme suit :

Bien que divers langages de programmation disposent désormais de leurs propres fonctions de bibliothèque de tri puissantes, ces implémentations sous-jacentes utilisent également ces algorithmes de tri de base ou avancés.

Il est très intéressant de comprendre ces algorithmes de tri complexes et d'expérimenter la subtilité de ces algorithmes de tri~

Tri Hill (tri shell) : le tri Hill est basé sur le tri par insertion, la différence est que Le tri par insertion est une comparaison des éléments adjacents (similaire au cas h = 1 dans Hill), tandis que le tri Hill est une comparaison et un remplacement de la distance h.

Facteur n constant dans le tri Hill, le tableau d'origine est divisé en différents groupes, chaque groupe est constitué de h éléments et il peut y avoir des éléments redondants. Bien entendu, h diminue également à chaque fois qu'il est bouclé (h=h/n). Le premier cycle commence à partir de l'index h. Une idée du tri Hill est de se diviser en groupes pour trier.

Pour comprendre ces algorithmes, il est préférable d'avoir des schémas. Commençons par le code.

<?php
/**
 * 希尔排序
 */
function shell_sort(array $arr){
  // 将$arr按升序排列
  $len = count($arr);
  $f = 3;// 定义因子
  $h = 1;// 最小为1
  while ($h < $len/$f){
    $h = $f*$h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
  }
  while ($h >= 1){ // 将数组变为h有序
    for ($i = $h; $i < $len; $i++){ // 将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中 （算法的关键
      for ($j = $i; $j >= $h; $j -= $h){
        if ($arr[$j] < $arr[$j-$h]){
          $temp = $arr[$j];
          $arr[$j] = $arr[$j-$h];
          $arr[$j-$h] = $temp;
        }
        //print_r($arr);echo &#39;<br/>&#39;; // 打开这行注释，可以看到每一步被替换的情形
      }
    }
    $h = intval($h/$f);
  }
  return $arr;
}
$arr = array(14, 9, 1, 4, 6, -3, 2, 99, 13, 20, 17, 15, 3);
$shell = shell_sort($arr);
echo &#39;<pre class="brush:php;toolbar:false">&#39;;
print_r($shell);
/**
*
Array
(
[0] => -3
[1] => 1
[2] => 2
[3] => 3
[4] => 4
[5] => 6
[6] => 9
[7] => 13
[8] => 14
[9] => 15
[10] => 17
[11] => 20
[12] => 99
)
)
*
*/

Articles qui pourraient vous intéresser :

Explication de la façon dont PHP utilise des clés personnalisées pour crypter et déchiffrer les données

Explication de quatre fonctions simples de calcul d'opérations arithmétiques implémentées par PHP

Explication sur la façon d'implémenter un nombre non fixe de paramètres dans le routage Laravel

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!