Rūšiavimo pasirinkimas priklauso nuo kelių savybių: laiko sudėtingumo, stabilumo, vietoje atminties naudojimo ir duomenų pobūdžio. Nėra vieno rūšiavimo, kuris būtų geriausia visais atvejais.
Rūšiavimo pasirinkimas priklauso nuo kelių savybių: laiko sudėtingumo, stabilumo, vietoje atminties naudojimo ir duomenų pobūdžio. Nėra vieno rūšiavimo, kuris būtų geriausia visais atvejais.
| Algoritmas | Vid. laikas | Blogiausias | Stabilus | Vietoje |
|---|---|---|---|---|
| Insertion | O(n²) | O(n²) | Taip | Taip |
| Merge | O(n log n) | O(n log n) | Taip | Ne |
| Quick | O(n log n) | O(n²) | Ne | Taip |
| Heap | O(n log n) | O(n log n) | Ne | Taip |
# Most languages ship a tuned hybrid; prefer it in production
sorted(data, key=lambda x: x.priority) # stable Timsort in Python
Nerašykite rūšiavimo rankiniu būdu, jei nėra konkrečios priežasties — bibliotekos rūšiavimai (Timsort, introsort) yra patikrinti hibridai.
Rūšiavimo pritaikymas duomenims ir reikalavimams išvengia ir neproduktyvaus laiko, ir subtilių klaidų (pavyzdžiui, stabilumo praradimo).
Supratę kompromisus, sužinosite, kodėl standartinės bibliotekos pasirinktos hibridai, tokie kaip Timsort ir introsort.
Šis palyginamasis sprendimas — o ne vieno algoritmo įsimintinimas — yra tai, ką vertina tikra inžinerija ir interviu.