Methoden und Prinzipien zum Schreiben des Einfügungssortierungsalgorithmus in Java

Schritte und Ideen des Einfügesortieralgorithmus

Einfügesortierung ist ein einfacher und intuitiver Sortieralgorithmus. Seine Grundidee besteht darin, die zu sortierenden Elemente an der entsprechenden Position der sortierten Reihenfolge einzufügen.

Die spezifischen Schritte sind wie folgt:

1. Zuerst teilen wir das Array in zwei Teile: den sortierten Teil und den unsortierten Teil. Zunächst gibt es im sortierten Teil nur ein Element, nämlich das erste Element des Arrays.
2. Wir nehmen der Reihe nach ein Element aus dem unsortierten Teil heraus, vergleichen es nacheinander mit den Elementen im sortierten Teil und finden die entsprechende Position zum Einfügen.
3. Während des Vergleichsprozesses verschieben wir die Elemente im sortierten Teil nach hinten, um Platz für die eingefügten Elemente zu schaffen.
4. Schließlich fügen wir alle Elemente des unsortierten Teils an den entsprechenden Positionen des sortierten Teils ein und die Sortierung ist abgeschlossen.

Das Folgende ist ein Beispielcode zum Schreiben des Einfügungssortierungsalgorithmus in der Java-Sprache:

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; 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;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 9, 3};
        System.out.println("原数组：");
        printArray(arr);
        insertionSort(arr);
        System.out.println("排序后的数组：");
        printArray(arr);
    }

    public static void printArray(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

In diesem Codebeispiel definieren wir eine insertionSort-Methode, die ein ganzzahliges Array als Parameter akzeptiert und einen ausführt Funktion für das Array. Führt eine Einfügungssortierung durch. Wir verwenden n, um die Länge des Arrays darzustellen, und for, um die Elemente des unsortierten Teils zu durchlaufen. Bei jedem Durchlauf speichern wir das aktuelle Element arr[i] in der Variablen key und durchlaufen dann den sortierten Teil vorwärts, um die geeignete Position zum Einfügen des -Schlüssels zu finden . Während des Vergleichsprozesses verschieben wir das größere Element um eine Position nach hinten, um Platz für key zu schaffen. Abschließend fügen wir den key an der richtigen Position ein und die Sortierung ist abgeschlossen. insertionSort方法，它接受一个整数数组作为参数，并对数组进行插入排序。我们用n表示数组的长度，并使用for循环遍历未排序部分的元素。在每一次遍历中，我们将当前元素arr[i]保存到key变量中，然后向前遍历已排序部分，找到合适的位置插入key。在比较的过程中，我们将较大的元素往后移动一位，为key腾出位置。最后，我们将key插入到正确的位置上，排序完成。

在main方法中，我们初始化一个整数数组arr，并调用insertionSort方法对数组进行排序。最后，我们调用printArray

In der Methode main initialisieren wir ein ganzzahliges Array arr und rufen die Methode insertionSort auf, um das Array zu sortieren. Schließlich rufen wir die Methode printArray auf, um das sortierte Array zu drucken.

Durch Ausführen des obigen Codes können Sie die folgende Ausgabe erhalten:

原数组：
5 2 8 1 9 3 
排序后的数组：
1 2 3 5 8 9 

Die zeitliche Komplexität des Einfügungssortierungsalgorithmus beträgt O(n^2), wobei n die Länge des Arrays ist. Obwohl der Einfügungssortierungsalgorithmus eine hohe zeitliche Komplexität aufweist, ist seine Implementierung einfach und für die Array-Sortierung im kleinen Maßstab geeignet. Gleichzeitig weist der Einfügungssortierungsalgorithmus in praktischen Anwendungen auch die Eigenschaften der Stabilität auf. 🎜

Das obige ist der detaillierte Inhalt vonMethoden und Prinzipien zum Schreiben des Einfügungssortierungsalgorithmus in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!