Welche Sortieralgorithmen gibt es für Arrays?

Array-Sortieralgorithmus wird verwendet, um Elemente in einer bestimmten Reihenfolge anzuordnen. Zu den gängigen Arten von Algorithmen gehören: Blasensortierung: Vertauschen Sie Positionen durch Vergleichen benachbarter Elemente. Auswahlsortierung: Finden Sie das kleinste Element und tauschen Sie es an die aktuelle Position aus. Einfügungssortierung: Elemente einzeln an der richtigen Position einfügen. Schnelle Sortierung: Divide-and-Conquer-Methode, wählen Sie das Pivot-Element aus, um das Array zu teilen. Zusammenführungssortierung: Teilen und Erobern, rekursives Sortieren und Zusammenführen von Unterarrays.

Einführung und Praxis des Array-Sortieralgorithmus

In der Informatik ist der Array-Sortieralgorithmus ein Algorithmus, der zum Anordnen einer Menge von Elementen in einer bestimmten Reihenfolge verwendet wird. Sortieralgorithmen werden aufgrund ihrer Prinzipien und Effizienz in viele verschiedene Typen unterteilt. Im Folgenden werden einige gängige Array-Sortieralgorithmen vorgestellt und ihre Verwendung anhand praktischer Fälle demonstriert.

Bubble Sort

Bubble Sort ist ein einfacher und leicht verständlicher Sortieralgorithmus. Sein Grundprinzip besteht darin, die Größen benachbarter Elemente nacheinander zu vergleichen und sie auszutauschen, wenn das vorherige Element größer als das nächste ist Positionen. Dieser Vorgang wird wiederholt, bis alle Elemente in Ordnung sind.

def bubble_sort(arr):
    for i in range(len(arr) - 1):
        for j in range(len(arr) - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

Auswahlsortierung

Auswahlsortierung ist ebenfalls ein einfacher Sortieralgorithmus. Sein Prinzip besteht darin, das kleinste Element des unsortierten Teils zu finden und es mit dem aktuellen Positionselement auszutauschen. Anschließend wiederholen Sie den Vorgang, bis alle Elemente in Ordnung sind.

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

Einfügungssortierung

Einfügungssortierung ist ein Sortieralgorithmus, der auf Einfügungsoperationen basiert. Sein Grundprinzip besteht darin, Elemente einzeln an der richtigen Position des sortierten Teils einzufügen, bis alle Elemente in der richtigen Reihenfolge angeordnet sind.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

Quicksort

Quicksort ist ein Divide-and-Conquer-Sortieralgorithmus, der ein Array durch Auswahl eines Pivot-Elements in zwei Unterarrays aufteilt und die beiden Unterarrays dann rekursiv sortiert, bis alle Elemente in Ordnung sind.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

Merge-Sortierung

Merge-Sortierung ist ein stabiler und effizienter Divide-and-Conquer-Sortieralgorithmus. Sein Prinzip besteht darin, das Array rekursiv in kleinere Unterarrays zu unterteilen und die Unterarrays dann zu sortieren und zusammenzuführen, bis alle Elemente vorhanden sind In der richtigen Reihenfolge angeordnet.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])
    return merge(left_half, right_half)

def merge(left, right):
    merged = []
    left_idx, right_idx = 0, 0
    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] <= right[right_idx]:
            merged.append(left[left_idx])
            left_idx += 1
        else:
            merged.append(right[right_idx])
            right_idx += 1
    merged.extend(left[left_idx:])
    merged.extend(right[right_idx:])
    return merged

Praktischer Fall

Angenommen, wir haben eine ungeordnete Liste arr = [5, 2, 8, 3, 1, 9], wir können sie mit dem Schnellsortierungsalgorithmus sortieren. Der Code lautet wie folgt:

arr = [5, 2, 8, 3, 1, 9]
sorted_arr = quick_sort(arr)
print(sorted_arr)  # 输出：[1, 2, 3, 5, 8, 9]

Das obige ist der detaillierte Inhalt vonWelche Sortieralgorithmen gibt es für Arrays?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!