Tai trys paprasti O(n²) palyginimo rūšiavimo algoritmai. Jie lėti su didžiais įvestimis, tačiau lengvai suprantami ir naudingi rūšiavimo mechanikai mokyti.
Tai trys paprasti O(n²) palyginimo rūšiavimo algoritmai. Jie lėti su didžiais įvestimis, tačiau lengvai suprantami ir naudingi rūšiavimo mechanikai mokyti.
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 | Best | Worst | Stable | In-place |
|---|---|---|---|---|
| Bubble | O(n) | O(n²) | Yes | Yes |
| Selection | O(n²) | O(n²) | No | Yes |
| Insertion | O(n) | O(n²) | Yes | Yes |
Insertion sort tikrai greitas mažiems arba beveik surūšytiems masyvams ir naudojamas hibridiniuose rūšiavimuose. Venkite visų trijų su dideliais nesurūšytais duomenimis — naudokite O(n log n) rūšiavimą.
Šie rūšiavimai sukuria intuiciją apie invariantus, keitus ir stabilumą, prieš pradėdami dirbti su sudėtingais algoritmais.
Insertion sort ypač pasirodo gamybos rūšiavimuose (tokiuose kaip Timsort) mažiems sub-masyvams.
Supratimas, kodėl jie yra O(n²), daro perėjimą prie O(n log n) rūšiavimo prasmingą.