Detaillierte Erläuterung des Sortieralgorithmus für direkte Einfügung und der zugehörigen Java-Versionscode-Implementierung

Direkte Einfügungssortierung

Die Idee der direkten Einfügungssortierung ist wie folgt:
1 Teilen Sie das zu sortierende Array zunächst in Das erste Ein Element gilt als sortiert.
2. Suchen Sie ausgehend vom zweiten Element die entsprechende Position des Elements im sortierten Subarray und fügen Sie es an dieser Position ein.
3. Wiederholen Sie den obigen Vorgang, bis das letzte Element in das geordnete Subarray eingefügt ist.
4. Sortierung abgeschlossen.

Beispiel:
Die Idee ist sehr einfach, aber der Code ist nicht so einfach zu schreiben wie die Blasensortierung. Wie ermitteln Sie zunächst den geeigneten Standort? Links größer oder gleich, rechts kleiner oder gleich? Nein, es sind viele Randbedingungen zu berücksichtigen und es gibt zu viele Urteile. Zweitens erfordert das Einfügen von Elementen in ein Array zwangsläufig das Verschieben einer großen Anzahl von Elementen. Wie kann deren Bewegung gesteuert werden?
Eigentlich ist das kein Problem des Algorithmus selbst, sondern hat etwas mit der Programmiersprache zu tun. Manchmal ist der Algorithmus selbst schon sehr ausgereift und muss im Hinblick auf die jeweilige Programmiersprache noch leicht modifiziert werden. Wir reden hier über den Java-Algorithmus, also reden wir über Java.
Um das obige Problem zu lösen, verfeinern wir den zweiten Schritt etwas. Wir beginnen den Vergleich nicht an der Startposition des Unterarrays, sondern beginnen den Vergleich am Ende des Unterarrays in umgekehrter Reihenfolge. Solange es größer ist als die einzufügende Zahl, gehen wir rückwärts. Bis die Zahl nicht größer als diese Zahl ist, wird die einzufügende Zahl an dieser freien Stelle platziert. Daher können wir den folgenden Code schreiben:
InsertArray.java

public class InsertArray {
  // 数组
  private long[] arr;
 
  // 数组中有效数据的大小
  private int elems;
 
  // 默认构造函数
  public InsertArray() {
    arr = new long[50];
  }
 
  public InsertArray(int max) {
    arr = new long[max];
  }
 
  // 插入数据
  public void insert(long value) {
    arr[elems] = value;
    elems++;
  }
 
  // 显示数据
  public void display() {
    for (int i = 0; i < elems; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }
 
  // 插入排序
  public void insertSort() {
    long select = 0L;
    for(int i = 1; i < elems; i++) {
      select = arr[i];
      int j = 0;
      for(j = i;j > 0 && arr[j - 1] >= select; j--) {
        arr[j] = arr[j - 1];
      }
      arr[j] = select;
    }
  }
}

Testklasse:
TestInsertArray.java

public class TestInsertArray {
  public static void main(String[] args) {
    InsertArray iArr = new InsertArray();
    iArr.insert(85);
    iArr.insert(7856);
    iArr.insert(12);
    iArr.insert(8);
    iArr.insert(5);
    iArr.insert(56);
 
    iArr.display();
    iArr.insertSort();
    iArr.display();
  }
 
}

Algorithmusleistung/-komplexität
Jetzt Lassen Sie uns die zeitliche Komplexität des Direkteinfügungsalgorithmus diskutieren. Unabhängig von der Eingabe führt der Algorithmus immer n-1 Sortierrunden durch. Da jedoch der Einfügepunkt jedes Elements unsicher ist und stark von den Eingabedaten beeinflusst wird, ist seine Komplexität nicht sicher. Wir können die besten, schlechtesten und durchschnittlichen Situationen besprechen.
1. Bester Fall: Aus den Eigenschaften des Algorithmus ist ersichtlich, dass es am besten ist, wenn das zu sortierende Array selbst in positiver Reihenfolge vorliegt (das Array ist in Ordnung und die Reihenfolge stimmt mit der erforderlichen Reihenfolge überein). Dies ist die aufsteigende Reihenfolge basierend auf der Prämisse unserer Diskussion. Der Grund dafür ist, dass in diesem Fall jedes Element nur einmal verglichen und nicht verschoben werden muss. Die zeitliche Komplexität des Algorithmus beträgt O(n);
2. Der schlimmste Fall ist offensichtlich, wenn das zu sortierende Array in umgekehrter Reihenfolge ist. In diesem Fall beträgt unsere Anzahl an Vergleichen in jeder Runde -1, Die Anzahl der Zuweisungen beträgt i. Der Gesamtgrad ist die Summe der ersten n Terme der Reihe 2n-1, also n^2. Die zeitliche Komplexität des Algorithmus beträgt O(n^2);
3 Durch Analyse können wir den durchschnittlichen Fallalgorithmus erhalten. Die Anzahl der Operationen beträgt ungefähr (n^2)/2 (Hinweis: Die Berechnung hier basiert auf Zuweisung und Vergleich. Wenn sie auf Bewegung und Vergleich basiert, beträgt sie ungefähr n^2 /4). Offensichtlich ist die Zeitkomplexität immer noch O(n^2).
Was die räumliche Komplexität des Algorithmus betrifft, werden alle Bewegungen innerhalb der Daten ausgeführt. Der einzige Aufwand besteht darin, dass wir eine temporäre Variable (in einigen Datenstrukturbüchern als „Sentinel“ bezeichnet) einführen Leerzeichen) ist O(1).

Algorithmusstabilität
Da Sie nur eine Position finden müssen, die nicht größer als die aktuelle Zahl ist, und keinen Austausch durchführen müssen, ist die Direkteinfügungssortierung eine stabile Sortiermethode.

Algorithmusvariante
Wenn viele Daten sortiert werden müssen, verursacht die Suche von hinten nach vorne viel Aufwand. Um die Suchgeschwindigkeit zu verbessern, wird die binäre Suche (Binary Search) benötigt ) kann zur Leistungsoptimierung verwendet werden. Da die binäre Suche sehr effizient ist und die Komplexität von O(㏒n) gewährleistet, kann sie die Sucheffizienz erheblich verbessern, wenn viele Daten vorhanden sind oder die Eingabedaten zum Worst-Case tendieren. In manchen Büchern wird diese Methode als „Half-Insertion-Sortierung“ bezeichnet. Die Code-Implementierung ist relativ kompliziert und ich werde sie veröffentlichen, wenn ich in Zukunft Zeit habe.
Darüber hinaus gibt es eine 2-Wege-Einfügungssortierung und eine Tabelleneinfügungssortierung. Die 2-Wege-Einfügungssortierung wurde auf der Grundlage der Halbeinfügungssortierung weiter verbessert und die Anzahl der Bewegungen wurde stark reduziert, etwa n^2/8. Es verringert jedoch nicht die Anzahl der Züge und verringert auch nicht die Komplexität. Die Sortierung durch Tabelleneinfügung ändert die Speicherstruktur vollständig und verschiebt keine Datensätze, erfordert jedoch die Pflege einer verknüpften Liste und das Ersetzen der verschobenen Datensätze durch Zeigeränderungen in der verknüpften Liste. Daher ist seine Komplexität immer noch O(n^2).
Informationen zur 2-Wege-Einfügungssortierung und Tabelleneinfügungssortierung finden Sie im Buch „Data Structure“, herausgegeben von Yan Weimin und Wu Weimin.

Anwendbare Szenarien des Algorithmus
Aufgrund der Komplexität von O(n^2) ist die Einfügungssortierung nicht anwendbar, wenn das Array groß ist. Es ist jedoch eine gute Wahl, wenn die Daten relativ klein sind, und wird im Allgemeinen als Erweiterung der Schnellsortierung verwendet. Beispielsweise wird im Sortieralgorithmus von STL und im qsort-Algorithmus von stdlib die Einfügungssortierung als Ergänzung zur Schnellsortierung zum Sortieren einer kleinen Anzahl von Elementen verwendet. Ein weiteres Beispiel: Bei der Implementierung der in JDK 7 verwendeten Sortiermethode java.util.Arrays wird die Einfügungssortierung verwendet, wenn die Länge des zu sortierenden Arrays weniger als 47 beträgt.

Ausführlichere Erläuterungen zum Direkteinfügungssortieralgorithmus und zugehörige Artikel zur Implementierung des Java-Versionscodes finden Sie auf der chinesischen PHP-Website!