Dies sind drei einfache O(n²) Vergleichssortierungen. Sie sind langsam bei großen Eingaben, aber leicht zu verstehen und nützlich zum Lehren der Sortierungsmechanik.
Dies sind drei einfache O(n²) Vergleichssortierungen. Sie sind langsam bei großen Eingaben, aber leicht zu verstehen und nützlich zum Lehren der Sortierungsmechanik.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i] # element to place
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # shift bigger elements right
j -= 1
arr[j + 1] = key # drop key into the gap
return arr
insertion_sort([5, 2, 4, 1]) # -> [1, 2, 4, 5]
| Sort | Beste | Schlechteste | Stabil | In-Place |
|---|---|---|---|---|
| Bubble | O(n) | O(n²) | Ja | Ja |
| Selection | O(n²) | O(n²) | Nein | Ja |
| Insertion | O(n) | O(n²) | Ja | Ja |
Insertion Sort ist tatsächlich schnell für kleine oder fast sortierte Arrays und wird in Hybrid-Sorters verwendet. Vermeiden Sie alle drei bei großen unsortierten Daten — verwenden Sie stattdessen O(n log n) Sorts.
Diese Sorts bauen Intuition für Invarianten, Vertauschungen und Stabilität auf, bevor Sie sich mit fortgeschrittenen Algorithmen auseinandersetzen.
Insertion Sort taucht insbesondere in Produktions-Sorts (wie Timsort) für winzige Sub-Arrays auf.
Zu wissen, warum sie O(n²) sind, macht den Sprung zu O(n log n) Sorts sinnvoll.