Wie implementiert man einen Einfügungssortierungsalgorithmus in Java?

1. Grundidee

Die Algorithmusbeschreibung der Einfügungssortierung (Insertion-Sort) ist ein einfacher und intuitiver Sortieralgorithmus. Es funktioniert, indem es eine geordnete Sequenz erstellt. Bei unsortierten Daten scannt es die sortierte Sequenz von hinten nach vorne, findet die entsprechende Position und fügt sie ein.

2. Algorithmusanalyse

1. Algorithmusbeschreibung

Im Allgemeinen wird die Einfügungssortierung im Array mithilfe von In-Place implementiert. Der spezifische Algorithmus wird wie folgt beschrieben:

• Beginnen Sie mit dem ersten Element, das als sortiert betrachtet werden kann;

• Nehmen Sie das nächste Element heraus und scannen Sie es von hinten nach vorne in der Reihenfolge der sortierten Elemente

Wenn das Element (sortiert) größer als das neue Element ist, verschieben Sie das Element an die nächste Position.
Wiederholen Sie Schritt 3, bis Sie die Position gefunden haben, an der das sortierte Element kleiner oder gleich dem neuen Element ist

• Fügen Sie das neue Element ein. Nachdem Sie die Position erreicht haben, wiederholen Sie die Schritte 2 bis 5.

• 2. Prozessanalyse
• (1), markieren Sie das erste Element (1) als sortiert.

(2), extrahieren Sie das erste unsortierte Element (28).

(3) Finden Sie die Stelle, an der das extrahierte Element eingefügt wird, und vergleichen Sie es mit dem sortierten Element 1.

(4), 1 > 28 ist nicht wahr (Falsch), fügen Sie ein Element an der vorhandenen Position ein.

(5), finden Sie heraus, wo die extrahierten Elemente eingefügt werden sollen, und vergleichen Sie sie mit den sortierten Elementen 28.

(6), 28 > 3 ist festgelegt (True), dann wird das aktuell sortierte Element ({val1}) um 1 Leerstelle nach rechts verschoben.

(7) Finden Sie die Stelle, an der das extrahierte Element eingefügt wird. Vergleichen Sie es mit dem sortierten Element 1.

(8), 1 > 3 ist nicht wahr (Falsch), fügen Sie ein Element an der vorhandenen Position ein.

(9) und so weiter

Drei. Algorithmus-Implementierung

package com.algorithm.tenSortingAlgorithm;

import java.util.Arrays;

public class InsertionSort {
    private static void insertionSort(int[] arr) {
        int preIndex, current;
        for (int i = 1; i < arr.length; i++) {
            preIndex = i - 1;
            current = arr[i];
            while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + 1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex + 1] = current;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,28,3,21,11,7,6,18};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

Das obige ist der detaillierte Inhalt vonWie implementiert man einen Einfügungssortierungsalgorithmus in Java?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!