So implementieren Sie eine einfache Sortierung in Java

Sortieren ist eine sehr häufige und zentrale Operation in der Datenverarbeitung, obwohl die Wahrscheinlichkeit gering ist, dass wir sie in der tatsächlichen Projektentwicklung manuell implementieren müssen. Schließlich gibt es in jeder Klasse mehrere Implementierungen von Sortieralgorithmen Bibliothek. Dennoch ist es für uns von großem Nutzen, diese subtilen Ideen zu verstehen. Dieser Artikel gibt einen kurzen Überblick über die drei grundlegendsten Arten von Algorithmen: Auswahl, Bubbling und Einfügung.

Definieren Sie zunächst eine Funktion zum Austauschen von Array-Elementen, die beim Sortieren aufgerufen werden kann

/**
     * 交换数组元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a,int b){
        arr[a] = arr[a]+arr[b];
        arr[b] = arr[a]-arr[b];
        arr[a] = arr[a]-arr[b];
    }

Einfache Auswahlsortierung

Die einfache Auswahlsortierung ist der einfachste und intuitivste Algorithmus. Die Grundidee besteht darin, den kleinsten Wert aus den Datenelementen auszuwählen Das in jedem Durchgang sortierte Element (oder das größte) wird als erstes Element verwendet, bis alle Elemente sortiert sind. Die einfache Auswahlsortierung ist eine instabile Sortierung.

Wenn der Algorithmus implementiert ist, wird bei jeder Bestimmung des Mindestelements die erste Position durch ständigen Vergleich und Austausch zum aktuellen Minimum. Der Austausch ist ein relativ zeitaufwändiger Vorgang. Tatsächlich können wir leicht feststellen, dass dieser Austausch bedeutungslos ist, bevor das aktuelle Mindestelement vollständig bestimmt ist. Wir können eine Variable min festlegen, um für jeden Vergleich nur den Array-Index des kleineren Elements zu speichern. Wenn die Schleife endet, speichert diese Variable den Index des aktuell kleinsten Elements und führt dann die Austauschoperation aus. Die Code-Implementierung ist sehr einfach, werfen wir einen Blick darauf.

Code-Implementierung

/**
     * 简单选择排序
     *
     * @param arr
     */
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;//每一趟循环比较时，min用于存放较小元素的数组下标，这样当前批次比较完毕最终存放的就是此趟内最小的元素的下标，避免每次遇到较小元素都要进行交换。
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            //进行交换，如果min发生变化，则进行交换
            if (min != i) {
                swap(arr,min,i);
            }
        }
    }

Nachdem die einfache Auswahlsortierung oben optimiert wurde, bleibt die Anzahl der Vergleiche unabhängig von der ursprünglichen Anordnung des Arrays für Austauschoperationen unverändert. Im besten Fall gibt es keine Austauschbewegungen, wenn das Array vollständig geordnet ist erforderlich, im schlimmsten Fall, das heißt, wenn das Array in umgekehrter Reihenfolge ist, beträgt die Anzahl der Austausche n-1. Zusammenfassend ist die Zeitkomplexität O(n2)

Blasensortierung

Die Grundidee der Blasensortierung besteht darin, benachbarte Elemente paarweise zu vergleichen und in umgekehrter Reihenfolge auszutauschen. Auf diese Weise wird jeder Durchgang am kleinsten Oder das größte Element „schwebt“ nach oben und erreicht schließlich die vollständige Reihenfolge ,1,2,3], nach der Ausführung von zwei Blasen, also nach zwei äußeren Schleifen, werden 5 und 4 jeweils an die Endposition [1,2,3,4,5] angepasst. Zu diesem Zeitpunkt wurde nach der Ausführung der dritten Schleife noch kein einziger Austausch durchgeführt, was bedeutet, dass die verbleibenden Sequenzen bereits in Ordnung sind und der Sortiervorgang abgeschlossen werden kann. Werfen wir einen Blick auf den Code Wenn das ursprüngliche Array selbst geordnet ist (dies ist der beste Fall), können nur n-1 Vergleiche abgeschlossen werden. Wenn die Reihenfolge umgekehrt ist, beträgt die Anzahl der Vergleiche n-1+n-2+. ..+1=n (n-1)/2, die Anzahl der Austausche und die Anzahl der Vergleiche sind gleich. Daher beträgt seine zeitliche Komplexität immer noch O(n2). Insgesamt ist die Leistung der Blasensortierung immer noch etwas schlechter als die der oben genannten Auswahlsortierung.

Direkteinfügungssortierung

Die Grundidee der Direkteinfügungssortierung besteht darin, bei jedem Schritt einen zu sortierenden Datensatz in die zuvor sortierte Reihenfolge einzufügen, bis alle Elemente eingefügt sind.

Code-Implementierung

/**
     * 冒泡排序
     *
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = true;//设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已然完成。
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr,j,j+1);
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
    }

Einfache Einfügungssortierung Im besten Fall muss n-1 Mal verglichen werden, ohne Elemente auszutauschen, und im schlimmsten Fall beträgt die Zeitkomplexität O(n). immer noch O(n2). Wenn die Array-Elemente jedoch zufällig angeordnet sind, ist die Einfügungssortierung immer noch besser als die beiden oben genannten Sortierungen.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie eine einfache Sortierung in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!