Heim > Backend-Entwicklung > C++ > Welche Sortieralgorithmen gibt es für Arrays?

Welche Sortieralgorithmen gibt es für Arrays?

WBOY
Freigeben: 2024-06-02 22:33:59
Original
720 Leute haben es durchsucht

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.

Welche Sortieralgorithmen gibt es für Arrays?

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]
Nach dem Login kopieren

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]
Nach dem Login kopieren

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
Nach dem Login kopieren

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)
Nach dem Login kopieren

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
Nach dem Login kopieren

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]
Nach dem Login kopieren

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!

Verwandte Etiketten:
Quelle:php.cn
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage