Grundlegendes zum Auswahlsortierungsalgorithmus (mit Beispielen in Java)

Auswahlsortierung: Eine Schritt-für-Schritt-Anleitung

Selection Sort ist ein unkomplizierter Sortieralgorithmus. Es findet wiederholt das minimale Element aus dem unsortierten Teil der Liste und platziert es an den Anfang. Dieser Vorgang wird fortgesetzt, bis die gesamte Liste sortiert ist.

So funktioniert die Auswahlsortierung

Lassen Sie uns anhand eines Beispiels veranschaulichen, wie wir dieses Array in aufsteigender Reihenfolge sortieren:

Iteration 1:

Ziel ist es, das kleinste Element am Anfang zu platzieren. Wir beginnen mit der Annahme, dass das erste Element das Minimum ist.

Wir vergleichen das aktuelle Minimum mit jedem nachfolgenden Element und aktualisieren das Minimum, wenn ein kleineres Element gefunden wird.

Dies wird so lange fortgesetzt, bis das tatsächliche Minimum identifiziert ist.

Zuletzt tauschen wir das minimale Element mit dem ersten Element aus.

Das erste Element ist nun sortiert. Nachfolgende Iterationen berücksichtigen nur den unsortierten Teil.

Nachfolgende Iterationen:

Dieser Vorgang wird für jedes verbleibende unsortierte Element wiederholt.

Der Algorithmus iteriert n-1 Mal (wobei n die Länge des Arrays ist). Nach der fünften Iteration (für ein Array mit sechs Elementen) wird das letzte Element implizit sortiert.

Auswahlsortierungsimplementierung (Java):

import java.util.Arrays;

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

    public static void selectionSort(int[] arr) {
        int size = arr.length;

        // Iterate through the array size-1 times
        for (int i = 0; i < size - 1; i++) {
            int minIndex = i;
            // Find the minimum element in the unsorted part
            for (int j = i + 1; j < size; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // Swap the minimum element with the first unsorted element
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}

Ausgabe:

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

Komplexitätsanalyse:

• Zeitkomplexität: O(n²) in allen Fällen (am besten, durchschnittlich, schlechtesten). Die verschachtelten Schleifen werden unabhängig von der Eingabereihenfolge immer eine feste Anzahl von Malen ausgeführt.
• Raumkomplexität: O(1). Es handelt sich um einen In-Place-Algorithmus, der ständig zusätzlichen Speicherplatz benötigt.

Fazit:

Die O(n²)-Zeitkomplexität von Selection Sort macht es für große Datensätze ineffizient. Es eignet sich am besten für kleine Arrays oder Situationen, in denen Einfachheit Vorrang vor Leistung hat.

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