Heim  >  Artikel  >  Backend-Entwicklung  >  Verwenden Sie Python, um 8 wichtige Sortieralgorithmen zu implementieren – Hill-Sortierung

Verwenden Sie Python, um 8 wichtige Sortieralgorithmen zu implementieren – Hill-Sortierung

巴扎黑
巴扎黑Original
2016-11-26 11:51:53934Durchsuche

Die Grundidee der Hill-Sortierung:

Hill-Sortierung ist eine Verbesserung, die auf der Einfügungssortierung basiert, wenn mit angeordneten Arrays gearbeitet wird, und die Einfügungssortierung ist im Allgemeinen ineffizient, da nur eine Position vorhanden ist können jeweils verschoben werden. Die Hill-Sortierung sortiert also zuerst nach Gruppierung, bis das Gruppierungsinkrement 1 beträgt.

Beispiel:

arr = [49,38,04,97,76,13,27,49,55,65], wenn das Gruppierungsinkrement 5 ist, ist die rote Zahl eins Gruppe, Führen Sie eine Einfügungssortierung durch und durchlaufen Sie nacheinander

arr = [13,38,04,97,76,49,27,49,55,65]. Nachdem die Durchquerung abgeschlossen ist, wird die Gruppierung erhöht dekrementiert,

arr = [13,27,04,55,65,49,38,49,97,76] und führt dann die Einfügungssortierung für die Gruppe mit einem Gruppierungsinkrement von 2 fort, bis die Gruppierungsinkrement ist 1

Code:

Python-Code

def shell_sort(lists):

#Hill sorting

count = len (Listen)

Schritt = 2

Gruppe = Anzahl / Schritt

während Gruppe > 0: #Schleife durch Gruppeninkrementgruppierung

für i in range(0, group):

j = i + group

while j < count: #Der Index des Schlüsselwerts in der Gruppe, erhöht um Inkrement

k = j - Gruppe

Schlüssel = Listen[j]

während k >= 0: #Einfügung Sortierung in Gruppen

wenn Listen[k] >

                                                                          Listen[k + Gruppe],                                                                                                                                                                            seit 🎜>

Gruppe /= Schritt

Rückgabelisten 🎜>

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn