Detaillierte Analyse der Methode zur Implementierung des Hill-Sortieralgorithmus in PHP

Obwohl verschiedene Programmiersprachen mittlerweile über eigene leistungsstarke Sortierbibliotheksfunktionen verfügen, verwenden diese zugrunde liegenden Implementierungen auch diese grundlegenden oder erweiterten Sortieralgorithmen. Es ist immer noch sehr interessant, diese komplexen Sortieralgorithmen zu verstehen. In diesem Artikel wird hauptsächlich die Methode zur Implementierung des Hill-Sortierungsalgorithmus in PHP vorgestellt, das Prinzip der Hill-Sortierung kurz erläutert und die spezifischen Bedienfähigkeiten der Hill-Sortierung in PHP anhand von Beispielen analysiert . Es braucht Freunde, die darauf verweisen können, ich hoffe, es kann jedem helfen.

Hill-Sortierung (Shell-Sortierung): Die Hill-Sortierung basiert auf der Einfügungssortierung. Der Unterschied besteht darin, dass die Einfügungssortierung ein Vergleich benachbarter Sortierungen ist (ähnlich dem Fall von h = 1 in Hill), während die Hill-Sortierung eine Sortierung ist ist ein Vergleich und Ersatz der Distanz h.

Ein konstanter Faktor n bei der Hill-Sortierung. Das ursprüngliche Array ist in Gruppen unterteilt, jede Gruppe besteht aus h Elementen und es können redundante Elemente vorhanden sein. Natürlich nimmt auch h bei jeder Schleife ab (h=h/n). Der erste Zyklus beginnt mit Index h. Eine Idee der Hill-Sortierung besteht darin, sie zum Sortieren in Gruppen aufzuteilen.

Um diese Algorithmen zu verstehen, ist es am besten, Diagramme zu haben. Beginnen wir mit dem 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
)
)
*
*/

Hast du es gelernt? Beeilen Sie sich und probieren Sie es aus.

Verwandte Empfehlungen:

Detaillierte Erläuterung des Sortieralgorithmus

JS-Implementierung von Zählsortierungs- und Basissortierungsalgorithmen-Beispielen_Javascript-Fähigkeiten

Beispielanalyse grundlegender, häufig verwendeter Sortieralgorithmen in JavaScript

Das obige ist der detaillierte Inhalt vonDetaillierte Analyse der Methode zur Implementierung des Hill-Sortieralgorithmus in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!