Analyse détaillée de la méthode d'implémentation de l'algorithme de tri Hill en PHP

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.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. Il faut que les amis puissent s'y référer, j'espère que cela pourra aider tout le monde.

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 de ceux adjacents (similaire au cas de h = 1 dans Hill), tandis que le tri Hill est trié par 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 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
)
)
*
*/

L'avez-vous appris ? Dépêchez-vous et essayez-le.

Recommandations associées :

Explication détaillée de l'algorithme de tri

Implémentation JS de l'algorithme de tri par comptage et de tri par base examples_compétences javascript

Exemple d'analyse des algorithmes de tri de base couramment utilisés en JavaScript

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!