Grundlegendes zum Einfügungssortierungsalgorithmus (mit Beispielen in Java)

Einfügesortierung ist ein iterativer Sortieralgorithmus. Es erstellt ein sortiertes Subarray Element für Element, indem jedes unsortierte Element an der richtigen Position innerhalb des sortierten Subarrays eingefügt wird. Stellen Sie sich das Sortieren einer Spielkartenhand vor – Sie beginnen mit einer sortierten Karte und fügen dann jede weitere Karte an der richtigen Stelle zwischen den bereits sortierten Karten ein.

So funktioniert die Einfügungssortierung

Lassen Sie uns dies anhand eines Beispielarrays veranschaulichen, das wir in aufsteigender Reihenfolge sortieren möchten:

Erste Iteration:

Wir betrachten das erste Element als bereits sortiert. Der Algorithmus beginnt mit dem zweiten Element.

Vergleich von 2 mit 8, da 2 < 8, wir verschieben 8 nach rechts und fügen 2 nach links ein.

Zweite Iteration:

Wir vergleichen 6 mit dem sortierten Subarray (2, 8). 6 < 8, also 8 Verschiebungen nach rechts. Dann, seit 6 > 2, 6 wird rechts von 2 platziert.

Dieser Vorgang wird fortgesetzt, bis das gesamte Array sortiert ist.

Implementierung in Java

<code class="language-java">import java.util.Arrays;

public class InsertionSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}</code>

Der Code iteriert und nimmt jedes Element als key. Anschließend vergleicht es das key mit den Elementen im sortierten Teil und verschiebt größere Elemente nach rechts, bis die richtige Position für das key gefunden ist.

Zum Beispiel in der zweiten Iteration (i=2):

Das key ist 6. Die while-Schleife verschiebt Elemente, bis die richtige Position gefunden ist:

Zuletzt wird 6 eingefügt:

Ausgabe:

Unsortiertes Array: [8, 2, 6, 4, 9, 1] Sortiertes Array: [1, 2, 4, 6, 8, 9]

Komplexitätsanalyse

• Zeitkomplexität:
  • Best Case (O(n)): Bereits sortiertes Array.
  • Durchschnittlicher Fall (O(n²)): Zufällig angeordnete Elemente.
  • Worst Case (O(n²)): Reverse-sorted array.
• Raumkomplexität: O(1) (In-Place-Algorithmus)

Fazit

Die quadratische Zeitkomplexität der Einfügungssortierung macht sie für große Datensätze ineffizient. Es handelt sich jedoch um einen einfachen Algorithmus, der bei kleinen Datensätzen oder nahezu sortierten Daten gut funktioniert.

Das obige ist der detaillierte Inhalt vonGrundlegendes zum Einfügungssortierungsalgorithmus (mit Beispielen in Java). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!