Sortieren bezieht sich auf den Prozess der Anordnung von Daten in einer bestimmten Reihenfolge, typischerweise in aufsteigender oder absteigender Reihenfolge, basierend auf einer linearen Beziehung zwischen den Datenelementen.
Sortieren ist bei der Arbeit mit strukturierten Daten von entscheidender Bedeutung, da es einen effizienten Datenabruf ermöglicht, die Datenanalyse vereinfacht und die allgemeine Datenverwaltung verbessert.
Dieser Beitrag behandelt die folgenden Sortieralgorithmen: Blasensortierung, Auswahlsortierung, Einfügungssortierung, Zusammenführungssortierung und Schnellsortierung.
Bubble Sort durchläuft wiederholt das Array, vergleicht benachbarte Elemente und tauscht sie aus, wenn sie in der falschen Reihenfolge sind. Dieser Vorgang wird fortgesetzt, bis das Array sortiert ist, wobei größere Elemente bis zum Ende „sprudeln“.
Schritt 1: Beginnen
Schritt 2: i = 0
Schritt 3: Wenn ich < Länge(Array) – 1, gehe zu Schritt 4; Andernfalls gehen Sie zu Schritt 10
Schritt 4: j = 0
Schritt 5: Wenn j < Länge(Array) – i – 1, gehe zu Schritt 6; Andernfalls gehen Sie zu Schritt 3
Schritt 6: if array[j] > array[j + 1], gehe zu Schritt 7; Andernfalls gehen Sie zu Schritt 8
Schritt 7: Array[j] und array[j + 1] vertauschen
Schritt 8: j erhöhen; Gehen Sie zu Schritt 5
Schritt 9: i erhöhen; Gehen Sie zu Schritt 3
Schritt 10: Ende
def bubble_sort(arr): print("Array Before Sorting: ", end='') print(arr) for i in range(len(arr)): for j in range(len(arr)-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] print("Array After Sorting: ", end='') print(arr) # Main bubble_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])
Bester Fall: O(n)
Durchschnittlicher Fall: O(n^2)
Schlimmster Fall: O(n^2)
Selection Sort findet den kleinsten Wert im unsortierten Teil des Arrays und platziert ihn am Anfang dieses Teils.
Schritt 1: Beginnen
Schritt 2: i = 0
Schritt 3: Wenn ich < Länge(Array) – 1, gehe zu Schritt 4; Andernfalls gehen Sie zu Schritt 10
Schritt 4: Minimum_value = i; j = i + 1
Schritt 5: Wenn j < Länge(Array), gehe zu Schritt 6; Andernfalls gehen Sie zu Schritt 9
Schritt 6: if array[minimum_value] > array[j], gehe zu Schritt 7; Andernfalls gehen Sie zu Schritt 8
Schritt 7: Minimum_value = j
Schritt 8: j erhöhen; Gehen Sie zu Schritt 5
Schritt 9: Array[minimum_value] und array[i]
vertauschen
Schritt 10: i erhöhen; Gehen Sie zu Schritt 3
Schritt 11: Ende
def selection_sort(arr): print("Array Before Sorting: ", end='') print(arr) for i in range(len(arr) - 1): min_val = i for j in range(i + 1, len(arr)): if arr[j] < arr[min_val]: min_val = j arr[i], arr[min_val] = arr[min_val], arr[i] print("Array After Sorting: ", end='') print(arr) # Main selection_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])
Bester Fall: O(n^2)
Durchschnittlicher Fall: O(n^2)
Schlimmster Fall: O(n^2)
Einfügungssortierung erstellt das sortierte Array Element für Element, indem jedes Element aus dem unsortierten Teil entnommen und an der richtigen Position im sortierten Teil eingefügt wird.
Schritt 1: Beginnen
Schritt 2: i = 1
Schritt 3: Wenn ich < len(arr), gehe zu Schritt 4; Andernfalls gehen Sie zu Schritt 12
Schritt 4: key = arr[i]
Schritt 5: j = i - 1
Schritt 6: Wenn j >= 0 und arr[j] > Schlüssel, gehe zu Schritt 7; Andernfalls gehen Sie zu Schritt 10
Schritt 7: arr[j + 1] = arr[j]
Schritt 8: Dekrementieren Sie j um 1
Schritt 9: Gehen Sie zu Schritt 6
Schritt 10: arr[j + 1] = key
Schritt 11: i um 1 erhöhen; Gehen Sie zu Schritt 3
Schritt 12: Ende
def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key # Main arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6] print("Array Before Sorting:", arr) insertion_sort(arr) print("Array After Sorting:", arr)
Bester Fall: O(n)
Durchschnittlicher Fall: O(n^2)
Schlimmster Fall: O(n^2)
Merge Sort ist ein Divide-and-Conquer-Algorithmus, der das Array rekursiv in kleinere Unterarrays aufteilt, sie sortiert und dann wieder zusammenführt.
Sortieralgorithmus zusammenführen
Schritt 1: Beginnen
Schritt 2: Wenn Länge(Array) <= 1, Array zurückgeben; Gehen Sie zu Schritt 9
Schritt 3: mid_point = length(array) // 2
Schritt 4: left_half = array[:mid_point]
Schritt 5: right_half = array[mid_point:]
Schritt 6: sorted_left = merge_sort(left_half)
Schritt 7: sorted_right = merge_sort(right_half)
Schritt 8: return merge(sorted_left, sorted_right)
Schritt 9: Ende
Zusammenführungsfunktion
Schritt 1: Beginnen
Schritt 2: sorted_merge = []
Schritt 3: l = 0, r = 0
Schritt 4: Wenn l < len(links) und r < len(rechts), gehe zu Schritt 5; Andernfalls gehen Sie zu Schritt 9
Schritt 5: Wenn left[l] <= right[r], gehe zu Schritt 6; Andernfalls gehen Sie zu Schritt 7
Schritt 6: left[l] zu sorted_merge hinzufügen; Erhöhe l um 1
Schritt 7: right[r] zu sorted_merge hinzufügen; Erhöhe r um 1
Schritt 8: Gehen Sie zu Schritt 4
Schritt 9: Wenn l < len(links), gehe zu Schritt 10; Andernfalls gehen Sie zu Schritt 12
Schritt 10: left[l] zu sorted_merge hinzufügen; l um 1 erhöhen
Schritt 11: Gehen Sie zu Schritt 9
Schritt 12: Wenn r < len(rechts), gehe zu Schritt 13; Andernfalls gehen Sie zu Schritt 15
Schritt 13: right[r] zu sorted_merge hinzufügen; Erhöhe r um 1
Schritt 14: Gehen Sie zu Schritt 12
Schritt 15: Geben Sie sorted_merge
zurück
Schritt 16: Ende
def merge(left, right): sorted_merge = [] l = r = 0 while l < len(left) and r < len(right): if left[l] <= right[r]: sorted_merge.append(left[l]) l += 1 else: sorted_merge.append(right[r]) r += 1 while l < len(left): sorted_merge.append(left[l]) l += 1 while r < len(right): sorted_merge.append(right[r]) r += 1 return sorted_merge def merge_sort(arr): if len(arr) <= 1: return arr mid_point = len(arr) // 2 left_half = arr[:mid_point] right_half = arr[mid_point:] sorted_left = merge_sort(left_half) sorted_right = merge_sort(right_half) return merge(sorted_left, sorted_right) # Main arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6] print("Array Before Sorting:", arr) arr = merge_sort(arr) print("Array After Sorting:", arr)
Bester Fall: O(n log n)
Durchschnittlicher Fall: O(n log n)
Schlimmster Fall: O(n log n)
Quick Sort is an efficient, in-place sorting algorithm that uses a divide-and-conquer approach. It selects a pivot element and partitions the array around the pivot so that elements less than the pivot are on its left and elements greater than the pivot are on its right. This process is then recursively applied to the sub-arrays.
Quick Sort
Step 1: Begin
Step 2: If low < high, goto Step 3; else goto Step 6
Step 3: pivot_index = partition(arr, low, high)
Step 4: quicksort(arr, low, pivot_index - 1)
Step 5: quicksort(arr, pivot_index + 1, high)
Step 6: End
Partition Function
Step 1: Begin
Step 2: pivot = arr[high]
Step 3: left = low, right = high - 1
Step 4: if left <= right goto Step 5, else goto Step 9
Step 5: if arr[left] > pivot and arr[right] < pivot, swap arr[left] and arr[right]
Step 6: if arr[left] <= pivot, increment left
Step 7: if arr[right] >= pivot, decrement right
Step 8: goto Step 4
Step 9: swap arr[left] and arr[high]
Step 10: return left
Step 11: End
def partition(arr, low, high): pivot = arr[high] left = low right = high - 1 while left <= right: if arr[left] > pivot and arr[right] < pivot: arr[left], arr[right] = arr[right], arr[left] if arr[left] <= pivot: left += 1 if arr[right] >= pivot: right -= 1 arr[left], arr[high] = arr[high], arr[left] return left def quicksort(arr, low, high): if low < high: pivot_index = partition(arr, low, high) quicksort(arr, low, pivot_index - 1) quicksort(arr, pivot_index + 1, high) # Main arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6] print("Array Before Sorting:", arr) quicksort(arr, 0, len(arr) - 1) print("Array After Sorting:", arr)
Best Case : O(n log n)
Average Case : O(n log n)
Worst Case : O(n^2)
Das obige ist der detaillierte Inhalt vonSortieralgorithmen in Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!