Detaillierte Erläuterung gängiger in Java implementierter Sortieralgorithmen

Sortieralgorithmen sind ein wichtiges Konzept in der Informatik und zentraler Bestandteil vieler Anwendungen. Im täglichen Leben und bei der Arbeit müssen wir häufig Daten sortieren, z. B. Listen sortieren, Werte sortieren usw. Als weit verbreitete Programmiersprache bietet Java viele integrierte Sortieralgorithmen. Dieser Artikel bietet eine detaillierte Einführung in gängige Sortieralgorithmen, die in Java implementiert sind.

1. Bubble Sort

Bubble Sort ist einer der einfachsten, aber langsamsten Sortieralgorithmen. Es durchläuft das gesamte Array, vergleicht benachbarte Elemente und verschiebt größere Werte Schritt für Schritt nach rechts, um schließlich das größte Element an das Ende des Arrays zu verschieben. Dieser Vorgang ähnelt dem Vorgang, bei dem Blasen vom Grund des Wassers an die Oberfläche aufsteigen, daher der Name Blasensortierung.

Das Folgende ist der in Java implementierte Blasensortierungsalgorithmus:

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Zeitkomplexität: O(n^2)

2.

Auswahlsortierung ist ein weiterer einfacher Sortieralgorithmus, der kontinuierlich die kleinste unsortierte Sortierung durchführt Element und verschieben Sie es an das Ende des sortierten Abschnitts. Die Auswahlsortierung ähnelt der Blasensortierung, erfordert jedoch keinen ständigen Austausch von Elementen in jeder Iteration, was sie schneller macht.

Das Folgende ist der in Java implementierte Auswahlsortierungsalgorithmus:

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        int temp = arr[min];
        arr[min] = arr[i];
        arr[i] = temp;
    }
}

Zeitkomplexität: O(n^2)

3. Einfügungssortierung ist ein effizienterer Sortieralgorithmus das sortierte Array und fügen Sie das unsortierte Element an der richtigen Position ein. Die Einfügungssortierung eignet sich aufgrund weniger Swaps für kleinere Datensätze.

Das Folgende ist der in Java implementierte Einfügesortieralgorithmus:

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;
    }
}

Zeitkomplexität: O(n^2)

4. Quick Sort (Quick Sort)

Quick Sort ist ein effizienter Sortieralgorithmus, der Divide and Conquer verwendet Die Idee besteht darin, das Array in kleinere Unterarrays aufzuteilen, die Unterarrays dann rekursiv zu sortieren und sie zusammenzuführen, um das endgültige sortierte Ergebnis zu erhalten. Der Schlüssel zum schnellen Sortieren besteht darin, das mittlere Element auszuwählen und nach Größe zu sortieren.

Das Folgende ist der in Java implementierte Schnellsortierungsalgorithmus:

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

public static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

Zeitkomplexität: O(n log n)

5. Merge Sort (Merge Sort)

Merge Sort ist ein weiterer gängiger Sortieralgorithmus, der Punkte verwendet um das Array in kleinere Unterarrays aufzuteilen, diese dann einzeln zu sortieren und zusammenzuführen, um das endgültige sortierte Ergebnis zu erhalten. Die Zusammenführungssortierung ist im Allgemeinen langsamer als die Schnellsortierung, aber stabiler.

Das Folgende ist der in Java implementierte Zusammenführungssortierungsalgorithmus:

public static void mergeSort(int[] arr, int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

public static void merge(int[] arr, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int[] L = new int[n1];
    int[] R = new int[n2];
    for (int i = 0; i < n1; i++) {
        L[i] = arr[l + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[m + j + 1];
    }
    int i = 0, j = 0;
    int k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

Zeitkomplexität: O(n log n)

Fazit

Die oben genannten sind gängige Sortieralgorithmen in Java und ihre Implementierungsdetails. Die Blasensortierung und die Auswahlsortierung sind einfacher, weisen jedoch eine höhere zeitliche Komplexität auf; die Schnellsortierung ist schneller, die Zusammenführungssortierung ist jedoch stabil, aber langsamer. Bei der tatsächlichen Verwendung muss die Auswahl auf der Grundlage unterschiedlicher Datenproben und tatsächlicher Anforderungen getroffen werden.

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung gängiger in Java implementierter Sortieralgorithmen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!