So implementieren Sie den Hill-Sortieralgorithmus in Python

Algorithmusbeschreibung

Hill-Sortierung, auch „reduzierende inkrementelle Sortierung“ genannt, ist ein Sortieralgorithmus, der durch Optimierung der Einfügungssortierung erstellt wird. Seine Ausführungsidee besteht darin, die Elemente im Array in tiefgestellte Inkremente zu gruppieren, jede Gruppe von Elementen einzufügen und zu sortieren, das Inkrement zu reduzieren und die vorherigen Schritte zu wiederholen, bis das Inkrement 1 erreicht.

Im Allgemeinen beträgt die zeitliche Komplexität der Hill-Sortierung O(n1,3)~O(n2), was von der Inkrementgröße abhängt. Die räumliche Komplexität der Hill-Sortierung beträgt O(1), was ein instabiler Sortieralgorithmus ist. Bei der Hügelsortierung kann sich eine Bewegung eines Elements über mehrere Elemente erstrecken, was mehrere Bewegungen ausgleichen und die Effizienz verbessern kann.

Das Folgende ist eine aufsteigende Hill-Sortierung mit (Array-Länge/2) als anfänglichem Inkrement. Nach jeder Sortierrunde wird das Inkrement um die Hälfte reduziert.

Schritt eins:

Wie in Abbildung 2-28 gezeigt, gruppieren Sie ausgehend vom ersten Element nach Schritt 4. Es ist ersichtlich, dass bei einem Inkrement von 4 nur zwei Elemente in einer Gruppe vorhanden sind, andernfalls überschreitet der Index des Elements den Bereich des Arrays.

Schritt 2:

Führen Sie, wie in Abbildung 2-29 gezeigt, eine Einfügungssortierung für die Elemente in der Gruppe durch.

Schritt 3:

Wie in Abbildung 2-30 gezeigt, verwenden Sie weiterhin dieselbe Methode zum Gruppieren und fügen Sie die Elemente in die Gruppe ein und sortieren Sie sie, um sie zu ordnen.

Nachdem alle Zahlen im gesamten Array durchlaufen wurden, ist diese Sortierrunde beendet. Reduzieren Sie die Schrittweite um die Hälfte und fahren Sie mit der nächsten Sortierrunde fort.

Schritt 4:

Wie in Abbildung 2-31 gezeigt, ist bei einem Inkrement von 2 ersichtlich, dass die Elemente in jeder Gruppe zugenommen haben und die Gesamtzahl der Gruppen abgenommen hat. Fahren Sie mit dem Einfügen und Sortieren der Elemente in jeder Gruppe fort, bis jede Gruppe durchlaufen ist.

Schritt 5:

Die letzte Sortierrunde ist in Abbildung 2-32 dargestellt. Reduzieren Sie das Inkrement zu diesem Zeitpunkt erneut um 1, was der Einfügungssortierung des gesamten Arrays entspricht. Das heißt, die letzte Rundensortierung.

Nach der letzten Sortierrunde ist die gesamte Hügelsortierung beendet.

Code-Implementierung

Da in der for-Schleife das erste Element jeder Gruppe nicht eingefügt und sortiert werden muss und ihre Indizes zwischen 0 und Schritt-1 liegen, beginnt die Durchquerung ab dem Indexschritt.

Es ist zu beachten, dass Sie, wenn Sie den Ansatz im Flussdiagramm simulieren möchten, zwei Schleifen verwenden müssen: Zuerst gruppieren und dann die Elemente gleichzeitig in derselben Gruppe anordnen. Um die Effizienz zu verbessern, verwenden wir direkt eine for-Schleife. Jedes Mal, wenn eine Zahl durchlaufen wird, wird die Gruppe, in der sie sich befindet, eingefügt und sortiert. Dieser Durchlauf erfüllt auch die Reihenfolgeanforderungen der Einfügungssortierung. Bei der Einfügungssortierung muss der Wert des aktuellen Index geändert werden. Daher wird die Variable ind zum Speichern des aktuellen Index verwendet, um zu verhindern, dass er die for-Schleife beeinflusst.

Die gewöhnliche Einfügungssortierung entspricht der Hill-Sortierung mit einer Schrittweite von 1. Die Hill-Sortierung über Elemente hinweg ändert eigentlich nur die Schrittweite und unterscheidet sich logischerweise nicht von der gewöhnlichen Einfügungssortierung.

Hill-Sortiercode:

nums = [5,3,6,4,1,2,8,7]
def ShellSort(nums):
  step = len(nums)//2　　　　　　　　 #初始化增量为数组长度的一半
  while step > 0:　　　　　　　　　　 #增量必须是大于0的整数
   for i in range(step,len(nums)):　#遍历需要进行插入排序的数
     ind = i
     while ind >= step and nums[ind] < nums[ind-step]: #对每组进行插入排序
      nums[ind],nums[ind-step] = nums[ind-step],nums[ind]
      ind -= step
   step //= 2　　　　　　　　　　　#增量缩小一半
  print(nums)
ShellSort(nums)

Führen Sie das Programm aus. Das Ausgabeergebnis lautet:

[1,2,3,4,5,6,7,8]

Das obige ist der detaillierte Inhalt vonSo implementieren Sie den Hill-Sortieralgorithmus in Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!