Eine Erklärung, wie der Hill-Sortieralgorithmus in PHP implementiert wird

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 Betriebsfähigkeiten der PHP-Implementierung der Hill-Sortierung anhand von Beispielen analysiert

Das Beispiel in diesem Artikel beschreibt, wie der Hill-Sortieralgorithmus in PHP implementiert wird. Teilen Sie es wie folgt als Referenz mit allen:

Obwohl verschiedene Programmiersprachen mittlerweile über eigene leistungsstarke Sortierbibliotheksfunktionen verfügen, verwenden diese zugrunde liegenden Implementierungen auch diese grundlegenden oder erweiterten Sortieralgorithmen.

Es ist sehr interessant, diese komplexen Sortieralgorithmen zu verstehen und die Feinheit dieser Sortieralgorithmen zu erleben~

Hill-Sortierung (Shell-Sortierung): Die Hill-Sortierung basiert auf der Einfügungssortierung, der Unterschied liegt in der Einfügung Beim Sortieren handelt es sich um einen Vergleich benachbarter Werte (ähnlich dem Fall von h=1 in Hill), während es sich beim Hill-Sortieren um einen Vergleich und eine Ersetzung des Abstands h handelt.

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
)
)
*
*/

Artikel, die Sie interessieren könnten:

Eine Erklärung, wie PHP benutzerdefinierte Schlüssel zum Verschlüsseln und Entschlüsseln von Daten verwendet

Ein Beispiel für eine einfache, von PHP implementierte Rechenfunktion mit vier Arithmen

Erklärung zur Implementierung einer nicht festgelegten Anzahl von Parametern im Laravel-Routing

Das obige ist der detaillierte Inhalt vonEine Erklärung, wie der Hill-Sortieralgorithmus in PHP implementiert wird. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!