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

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):  
    #希尔排序  
    count = len(lists)  
    step = 2  
    group = count / step  
    while group > 0:  #通过group增量分组循环  
        for i in range(0, group):  
            j = i + group  
            while j < count:  #分组中key值的索引，通过增量自增  
                k = j - group  
                key = lists[j]  
                while k >= 0:  #分组中进行插入排序  
                    if lists[k] > key:  
                        lists[k + group], lists[k] = lists[k], key  
                    else: break  
                    k -= group  
                j += group  
        group /= step  
    return lists