Wenn Sie Programmierer sind, haben Sie bestimmt schon viel über das Sortieren gehört. Sortieren bedeutet grundsätzlich, die Elemente entweder in aufsteigender oder absteigender Reihenfolge anzuordnen. Es stehen so viele Sortieralgorithmen zum Sortieren der Elemente zur Verfügung, und jeder Algorithmus verfügt über unterschiedliche Sortiermethoden und unterschiedliche Komplexität. Es hängt also vom konkreten Szenario und der Anzahl der Elemente ab, welcher Algorithmus verwendet werden soll. Das Einfügen ist auch einer der am häufigsten verwendeten Sortieralgorithmen mit der Komplexität O(n^2) und wird so durchgeführt, wie wir die Spielkarten in unseren Händen sortieren. In diesem Thema lernen wir etwas über die Einfügungssortierung in Java.
Starten Sie Ihren kostenlosen Softwareentwicklungskurs
Webentwicklung, Programmiersprachen, Softwaretests und andere
Wie funktioniert die Einfügungssortierung in Java?
Lassen Sie uns die Funktionsweise der Einfügungssortierung anhand eines Beispiels verstehen.
Angenommen, es gibt ein Array mit dem Namen arr mit den unten genannten Elementen:
10 5 8 20 30 2 9 7
Schritt #1 – Einfügesortierung beginnt mit dem 2. Element des Arrays, d. h. 5, wobei das 1. Element des Arrays als in sich selbst sortiert betrachtet wird. Jetzt wird das Element 5 mit 10 verglichen, da 5 kleiner als 10 ist, also wird 10 um eine Position nach vorne verschoben und 5 davor eingefügt.
Das resultierende Array lautet nun:
5 10 8 20 30 2 9 7
Schritt #2 – Jetzt wird das Element arr[2], also 8, mit dem Element arr[1], also 10, verglichen. Da 8 kleiner als sein vorhergehendes Element 10 ist, wird es um eins verschoben Schritt vorwärts von seiner Position, und dann wird es mit 5 verglichen. Da 8 größer als 5 ist, wird es danach eingefügt.
Dann ist das resultierende Array:
5 8 10 20 30 2 9 7
Schritt #3 – Da nun Element 20 mit 10 verglichen wird, da es größer als 10 ist, bleibt es an seiner Position.
5 8 10 20 30 2 9 7
Schritt #4 – Element 30 wird mit 20 verglichen, und da es größer als 20 ist, werden keine Änderungen vorgenommen und das Array bleibt unverändert. Jetzt wäre das Array
5 8 10 20 30 2 9 7
Schritt #5 – Element 2 wird mit 30 verglichen, da es kleiner als 30 ist, wird es um eine Position nach vorne verschoben und dann nacheinander mit 20,10, 8, 5 verglichen Alle Elemente werden um 1 Position nach vorne verschoben und 2 wird vor 5 eingefügt.
Das resultierende Array ist:
2 5 8 10 20 30 9 7
Schritt #6 – Element 9 wird mit 30 verglichen, da es kleiner als 30 ist; Es wird nacheinander mit 20 und 10 verglichen, das Element wird um eine Position nach vorne verschoben und 9 wird vor 10 und nach 8 eingefügt.
Das resultierende Array ist:
2 5 8 9 10 20 30 7
Schritt #7 – Element 7 wird mit 30 verglichen, und da es kleiner als 30 ist, wird es mit 30, 20, 10, 9, 8 verglichen und alle Elemente werden um eine Position verschoben nacheinander voran und 7 wird vor 8 eingefügt.
Das resultierende Array würde wie folgt aussehen:
2 5 7 8 9 10 20 30
Auf diese Weise werden alle Elemente des Arrays mithilfe der Einfügesortierung sortiert, wobei der Vergleich mit dem vorhergehenden Element beginnt.
Beispiele zur Implementierung der Einfügungssortierung in Java
Insertion Sort in Java ist ein einfacher Sortieralgorithmus, der für alle kleinen Datensätze geeignet ist.
Code:
public class InsertionSort {
public static void insertionSort(int arr[]) { for (int j = 1; j < arr.length; j++) { int key = arr[j]; int i = j-1;
while ( (i > -1) && ( arr[i] > key ) ) { arr[i+1] = arr[i]; i--; }
arr[i+1] = key;
}
}
static void printArray(int arr[]) { int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i<len; i++)
System.out.print(arr[i] + " " );
System.out.println();
}
public static void main(String args[]){ int[] arr1 = {21,18,15,23,52,12,61};
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
}
}Nach dem Login kopieren
Ausgabe:
12 15 18 21 23 52 61
Erklärung:
- Im obigen Programm von Insertion Sort wird die Funktion insertSort() verwendet, um die ursprünglichen Array-Elemente zu sortieren. Die Sortierung beginnt beim zweiten Element, da das erste Element an sich als sortiert gilt. Die Schleife von „j“ beginnt also beim Index 1 des Arrays. „i“ ist die Variable, die den Index direkt vor dem „j“ verfolgt, um den Wert zu vergleichen.‘
- key’ ist die Variable, die den Wert des aktuellen Elements enthält, das in sortierter Position angeordnet werden soll. Die while()-Schleife wird ausgeführt, wenn der aktuelle Wert kleiner als der Wert ganz links ist, damit das Verschieben von Elementen verarbeitet werden kann und am Ende das Einfügen des aktuellen Elements an der rechten Position durchgeführt werden kann. Die Funktion printArray() wird verwendet, um das sortierte Array endgültig zu drucken.
1. Bester Fall
Bei der Einfügesortierung wäre der beste Fall, wenn alle Elemente des Arrays bereits sortiert sind. Wenn also ein Element mit seinem am weitesten links stehenden Element verglichen wird, ist es immer größer und daher wird kein Verschieben und Einfügen von Elementen verarbeitet. In diesem Fall wäre die Komplexität im besten Fall linear, d. h. O(n).
2. Schlimmster Fall
Im obigen Code der Einfügungssortierung wäre der schlimmste Fall, wenn das Array in umgekehrter Reihenfolge vorliegt, d Platzieren, verschieben und einfügen ist erledigt. In diesem Fall beträgt die Komplexität der Einfügungssortierung O(n^2).
3. Durchschnittlicher Fall
Selbst im Durchschnittsfall hat die Einfügungssortierung eine O(n^2)-Komplexität, bei der einige Elemente nicht verschoben werden müssen, während einige Elemente von ihren Positionen verschoben werden und die Einfügung an der richtigen Position durchgeführt wird.
4. Beste Verwendung
Einfügesortierung eignet sich am besten, wenn die Größe eines Arrays nicht sehr groß ist oder nur eine kleine Anzahl von Elementen sortiert werden muss, wobei fast alle Elemente sortiert sind und nur einige Änderungen vorgenommen werden müssen. Die Einfügungssortierung ist einer der schnellsten Algorithmen für kleine Arrays, sogar schneller als die Schnellsortierung. Tatsächlich verwendet Quicksort die Einfügungssortierung, wenn es seine kleinen Teile des Arrays sortiert.
Fazit
Die obige Erklärung zeigt deutlich die Funktionsweise und Implementierung von Insertion Sort in Java. Auch in anderen Programmiersprachen bleibt die Logik zur Durchführung der Einfügungssortierung dieselbe, nur die Syntax ändert sich. Vor der Implementierung eines Sortieralgorithmus ist es sehr wichtig, eine Analyse des Szenarios durchzuführen, in dem sortiert werden muss, da nicht jeder Sortieralgorithmus in alle Szenarien passt.
Das obige ist der detaillierte Inhalt vonEinfügungssortierung in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
