Direkte Sortierung der direkten Einfügung
Die Idee, die Sortierung direkt einzufügen, ist leicht zu verstehen. Es sieht so aus:
1. Teilen Sie das Array, das in zwei Teile sortiert werden soll: sortiert und ungeortiert. Am Anfang wird das erste Element als sortiert angesehen.
2. Beginnen Sie mit dem zweiten Element, finden Sie die entsprechende Position des Elements in der sortierten Subtarray und fügen Sie es ein.
3. Wiederholen Sie den obigen Vorgang, bis das letzte Element in das geordnete Subtarray eingefügt wird.
4. Sortieren ist abgeschlossen.
Beispiel:
Die Idee ist einfach, aber der Code ist nicht so einfach zu schreiben wie Blasensortierung. Wie kann man zunächst die richtige Position bestimmen? Größer als oder gleich dem linken, weniger oder gleich dem Recht? Nein, viele Grenzbedingungen müssen berücksichtigt werden, und es gibt zu viele Urteile. Zweitens erfordert das Einfügen von Elementen in ein Array unweigerlich eine große Anzahl von Elementen. Wie kann man ihre Bewegung kontrollieren?
Tatsächlich ist dies kein Problem mit dem Algorithmus selbst und hat etwas mit der Programmiersprache zu tun. Manchmal ist der Algorithmus selbst bereits sehr ausgereift und muss immer noch geringfügig geändert werden, wenn es um die spezifische Programmiersprache geht. Was wir hier sprechen, ist der Java -Algorithmus. Sprechen wir also über Java.
Um das obige Problem zu lösen, haben wir den zweiten Schritt eine kleine Verfeinerung vorgenommen. Wir beginnen nicht mit dem Vergleich aus der Ausgangsposition des Sub-Array, sondern inversen Vergleich vom Schwanz des Sub-Array. Solange es größer ist als die Zahl, die eingefügt werden muss, bewegen wir uns rückwärts. Bis die Zahl nicht größer als die Zahl ist, wird die zu eingefügte Zahl in dieser leeren Position platziert. Daher können wir den folgenden Code schreiben:
InsertArray.java
öffentliche Klasse InsertArray {// Array privat long [] arr; // die Größe gültiger Daten im Array Private Int Elems; // Standardkonstruktor public InsertArray () {arr = new Long [50]; } public InsertArray (int max) {arr = new long [max]; } // Daten public void Insert (langer Wert) {arr [elems] = value; Elems ++; } // Daten public void display () {für (int i = 0; i <elems; i ++) {System.out.print (arr [i]+"); } System.out.println (); } // sortieren public void InsertSort () {long select = 0l; für (int i = 1; i <elems; i ++) {select = arr [i]; int j = 0; für (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 (); }} Druckergebnis:
Algorithmus Leistung/Komplexität
Lassen Sie uns nun die zeitliche Komplexität des direkten Einfügungsalgorithmus diskutieren. Unabhängig von der Eingabe führt der Algorithmus immer N-1-Sortierrunden durch. Da der Insertionspunkt jedes Elements jedoch ungewiss ist und von den Eingabedaten stark beeinflusst wird, ist seine Komplexität nicht sicher. Wir können die besten, schlechtesten und durchschnittlichen Situationen diskutieren.
1. Bester Fall: Aus den Merkmalen des Algorithmus ist ersichtlich, dass, wenn das zu arrangierende Array selbst in einer positiven Reihenfolge ist (das Array ist bestellt und die Reihenfolge der erforderlichen Reihenfolge, die in unserer Diskussionsvoraussetzungen in aufsteigender Reihenfolge ist). Der Grund dafür ist, dass in diesem Fall jedes Element nur einmal verglichen werden muss und nicht bewegt werden muss. Die zeitliche Komplexität des Algorithmus ist o (n);
2. Schlimmster Fall: Wenn das zu arrangierende Array in umgekehrter Reihenfolge ist, ist es der schlimmste Fall. In diesem Fall lautet unsere Anzahl der Vergleiche pro Runde I-1 und die Anzahl der Zuordnungen i. Die Gesamtzahl der Male ist die Summe der ersten N-Begriffe der Serie 2n-1, dh n^2. Die zeitliche Komplexität des Algorithmus ist O (n^2);
3. Durchschnittlicher Situation: Aus der obigen Analyse können wir ermitteln, dass die Anzahl der Operationen des Algorithmus unter der durchschnittlichen Situation ungefähr (n^2)/2 beträgt (Hinweis: Die Berechnung hier basiert auf Zuordnung und Vergleich. Wenn sie auf Bewegung und Vergleich basiert, ist es ungefähr n^2/4). Offensichtlich ist die Zeitkomplexität immer noch O (n^2).
In Bezug auf die räumliche Komplexität des Algorithmus werden alle Bewegungen innerhalb der Daten durchgeführt. Der einzige Overhead ist, dass wir eine temporäre Variable eingeführt haben (einige Datenstrukturen werden in Büchern als "Sentinels" bezeichnet), so dass seine räumliche Komplexität (zusätzlicher Raum) o (1) ist.
Algorithmusstabilität
Da Sie nur eine Position finden müssen, die nicht größer als die aktuelle Zahl ist und nicht tauschen muss, ist es eine stabile Sortiermethode, die Sortierung direkt einzufügen.
Algorithmusvarianten
Wenn viele Daten angeordnet werden müssen, verursacht dies jedes Mal, wenn Sie von hinten nach vorne schauen. Um die Suchgeschwindigkeit zu verbessern, kann eine binäre Suche für die Leistungsoptimierung verwendet werden. Da die Effizienz der binären Suche sehr hoch ist, wird die Komplexität von O (n) sichergestellt, und die Suchseffizienz kann erheblich verbessert werden, wenn mehr Daten oder die Eingabedaten am schlimmsten sind. In einigen Büchern wird diese Methode als Sortierung von Falten und halben Einfügen bezeichnet. Die Code -Implementierung ist ziemlich kompliziert und kann veröffentlicht werden, wenn Sie in Zukunft Zeit haben.
Zusätzlich gibt es 2-Wege-Einsatzsarten und Tabelleneinsatzsarten. Die 2-Wege-Insertion-Sortierung wird auf der Grundlage der Faltung und der halben Einfügungssorte weiter verbessert, und die Anzahl der Bewegungen wird stark reduziert, etwa 2/8. Die Anzahl der Bewegungen vermeidet jedoch nicht und verringert das Komplexitätsniveau nicht. Die Tabelleneinfügungssortierung ändert die Speicherstruktur vollständig und verschiebt keine Datensätze. Eine verknüpfte Liste muss jedoch beibehalten werden, und der Zeiger der verknüpften Liste wird geändert, anstatt Datensätze zu verschieben. Daher ist seine Komplexität immer noch O (n^2).
Für die Sortierung von 2-Wege-Einfügen und die Sortierung von Tabellen können Sie auf das von Yan Weimin und Wu Weimin herausgegebene Buch "Datenstruktur" verweisen.
Algorithmus anwendbarer Szenarien
Die Sortierung der Insertion ist nicht anwendbar, wenn das Array aufgrund der Komplexität von O (n^2) groß ist. Wenn es jedoch relativ wenig Daten gibt, ist es eine gute Wahl, die im Allgemeinen als Erweiterung für die schnelle Sortierung verwendet wird. Zum Beispiel wird im Sortieralgorithmus von STL und im QSORT -Algorithmus von STDLIB die Sortierung des Inserts als Ergänzung zur Schnellsortierung verwendet und verwendet, um eine kleine Anzahl von Elementen zu sortieren. Beispielsweise wird in der Implementierung der Sortiermethode, die in JDK 7 Java.util.Arrays verwendet wird, wenn die Länge des zu sortierenden Arrays weniger als 47 beträgt, die Einfügungssortierung verwendet wird.