Dette er tre simple O(n²) sammenlignings-sorter. De er langsomme på store inputs, men nemme at forstå og nyttige til at undervise i sorterings mekanisme.
Dette er tre simple O(n²) sammenlignings-sorter. De er langsomme på store inputs, men nemme at forstå og nyttige til at undervise i sorterings mekanisme.
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 | Bedst | Værst | Stabil | In-place |
|---|---|---|---|---|
| Bubble | O(n) | O(n²) | Ja | Ja |
| Selection | O(n²) | O(n²) | Nej | Ja |
| Insertion | O(n) | O(n²) | Ja | Ja |
Insertion sort er genuint hurtig til små eller næsten-sorterede arrays og bruges inden i hybrid sorter. Undgå alle tre på stort usorteret data — brug O(n log n) sorter i stedet.
Disse sorter opbygger intuition for invarianter, bytninger og stabilitet, før du tackler avancerede algoritmer.
Insertion sort vises især inde i produktions sorter (som Timsort) til små sub-arrays.
At vide hvorfor de er O(n²) gør springet til O(n log n) sorter meningsfuldt.
Et bibliotek af IT-interviewspørgsmål med detaljerede svar — fra Junior til Senior.
Donér