Implementierung des Hill-Sortieralgorithmus

Hill Sort ist eine verbesserte Version der Direkteinfügungssortierung und auch gehört zu einer Einfügungssortierung. Die Verbesserung besteht darin, für jeden Durchlauf eine Schrittgröße festzulegen und dann eine direkte Einfügungssortierung durchzuführen. Nach Abschluss eines Durchlaufs wird die Schrittgröße halbiert, bis die Schrittgröße kleiner oder gleich 1 ist.

(Empfohlenes Tutorial: Java-Einführungs-Tutorial)

Seit jedem Bei jeder Bewegung wird eine Schrittweite verschoben, während die direkte Einfügungssortierung jeweils nur einen Schritt bewegt. Daher ist die Effizienz der Hill-Sortierung höher als die der direkten Einfügungssortierung.

(Empfehlung für Lernvideos: Java-Kurs )

Algorithmusimplementierung:

  public static void shellSort(int[] array) {
        int step = array.length;
        while (true) {
            step /= 2;
            for (int i = 0; i < step; i++) {
                for (int j = i + step; j < array.length; j += step) {
                    int tmp = array[j];
                    int k = j;
                    while (k >=step && array[k - step] > tmp) {//将大于tmp的数往后移
                        array[k] = array[k - step];
                        k-=step;
                    }
                    array[k] = tmp;//插入
                }
            }
            if (step <= 1)
                return;
        }
    }

Das obige ist der detaillierte Inhalt vonImplementierung des Hill-Sortieralgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!