Ausführliche Erläuterung von Beispielen für die Java-Hill-Sortierung

Dieser Artikel stellt hauptsächlich die Java-Datenstruktur und den Algorithmus der Hill-Sortierung vor und analysiert das Konzept, das Prinzip, die Implementierungsmethode und die damit verbundenen Vorsichtsmaßnahmen in Form von Beispielen. Freunde in Not können sich darauf beziehen

Die Beispiele in diesem Artikel beschreiben die Hill-Sortierung von Java-Datenstrukturen und -Algorithmen. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Was ich hier vorstellen möchte, ist die Hill-Sortierung (verkleinernde inkrementelle Sortiermethode).

Hill-Sortierung: funktioniert durch den Vergleich von Elementen, die einen bestimmten Abstand voneinander haben; der bei jedem Vergleich verwendete Abstand (Inkrement) nimmt mit fortschreitendem Algorithmus ab, bis bis zur letzten Sortierung nur noch benachbarte Elemente verglichen werden Durchgang von Elementen. Es handelt sich um eine Art Einfügungssortierung und eine Verbesserung des Direkteinfügungssortierungsalgorithmus.

Algorithmische Idee: Teilen Sie zuerst die zu sortierende Sequenz entsprechend einem bestimmten Inkrement d in mehrere Teilsequenzen auf, führen Sie eine direkte Einfügungssortierung für alle Elemente in jeder Teilsequenz durch und verwenden Sie dann ein kleineres Gruppieren Sie es in Schritten und sortieren Sie es dann in jeder Gruppe. Wenn das Inkrement auf 1 sinkt, wird die gesamte zu sortierende Zahl in eine Gruppe aufgeteilt und die Sortierung ist abgeschlossen. Hinweis: Der Wert des Inkrements – im Allgemeinen wird die Hälfte der Sequenz zum ersten Mal als Inkrement verwendet und dann jedes Mal halbiert, bis das Inkrement 1 beträgt.

Der Algorithmus-Implementierungscode lautet wie folgt:

package exp_sort;
public class ShellSort {
  public static void shell(int array[]) {
    int j;
    int average;
    //设置增量的值
    for (average = array.length / 2; average > 0; average /= 2) { //步长
      for (int i = average; i < array.length; i++) { //子序列进行直接插入排序
        int temp = array[i];
        for (j = i; j >= average && temp < array[j - average]; j -= average) {
          array[j] = array[j - average];
        }
        array[j] = temp;
      }
    }
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    shell(array);
  }
}

Algorithmusanalyse: Dieser Algorithmus fügt Elemente nach unterschiedlichen Kriterien ein und sortiert sie Schrittgröße: Wenn die Elemente zu Beginn sehr ungeordnet sind, ist die Schrittgröße am größten, sodass die Anzahl der Elemente beim Einfügen sehr gering ist und die Geschwindigkeit sehr hoch ist, wenn die Elemente grundsätzlich geordnet sind sehr klein und die Einfügungssortierung ist für geordnete Sequenzen sehr effizient. Daher ist die zeitliche Komplexität der Hill-Sortierung besser als bei O(n^2), also O(n^1,5), und die Sortiereffizienz ist viel höher als Einfügungssortierung . Aufgrund der mehrfachen Einfügungssortierung wissen wir, dass eine Einfügungssortierung stabil ist und die relative Reihenfolge derselben Elemente nicht ändert. Bei verschiedenen Einfügungssortierungsprozessen können sich jedoch dieselben Elemente in ihren jeweiligen Einfügungssortierungen bewegen, und letztendlich ändert sich auch ihre Stabilität sind gestört, daher ist die Schalensortierung instabil. Hill-Sortierung ist nicht so schnell wie der schnelle Sortieralgorithmus O(N*(logN)), daher eignet sie sich besser zum Sortieren mittelgroßer Daten, ist jedoch nicht die optimale Wahl zum Sortieren sehr großer Datenmengen . Aber es ist viel schneller als der O(N^2)-Komplexitätsalgorithmus. Und die Hill-Sortierung ist sehr einfach zu implementieren und der Algorithmuscode ist kurz und einfach. Darüber hinaus unterscheidet sich die Leistungseffizienz des Hill-Algorithmus im schlimmsten Fall nicht wesentlich vom Durchschnittsfall, während die Effizienz der schnellen Sortierung im schlimmsten Fall sehr schlecht ist.

【Verwandte Empfehlungen】

1. Besondere Empfehlung: Version „php Programmer Toolbox“ V0.1 herunterladen

2. Kostenloses Java-Video-Tutorial

3. YMP-Online-Handbuch

Das obige ist der detaillierte Inhalt vonAusführliche Erläuterung von Beispielen für die Java-Hill-Sortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!