acest articol face parte dintr-o serie care acoperă algoritmi de sortare în JavaScript. Puteți găsi restul seriei aici. Dacă sunteți nou în sortarea algoritmilor sau algoritmilor în general, citiți mai întâi acest lucru pentru a obține o bază solidă pentru a merge mai departe. Astăzi voi fi acoperind intrarile si iesirile de inserție fel. Sortarea inserției este mai complexă, dar puțin mai utilă decât sortarea cu bule. Cel mai rău caz pentru că este similar cu Bubble sort, dar cel mai bun caz îl face potrivit pentru momentele în care sunteți destul de sigur că o listă aproape sortată sau probabil deja sortată. Să vedem imaginea de ansamblu.
sortarea inserției funcționează uitându-se la fiecare element dintr-o listă (începând cu al doilea element) și comparându-l cu elementul anterior. Dacă elementul anterior este mai mare, acestea sunt schimbate. Aceasta continuă până când elementul este mai mic, moment în care facem același lucru pentru următorul element din listă.
sortarea inserției nu este atât de Rea.. atâta timp cât îl folosiți în circumstanțele potrivite.
- este mai rapid decât majoritatea algoritmilor de sortare O(N log n) pentru liste mici.
- este extrem de eficient de memorie care necesită doar O(1) spațiu auxiliar pentru elementul unic care este mutat.
- este stabil — elementele egale apar în aceeași ordine în lista sortată.
- este adaptiv — este rapid atunci când sortați în mare parte liste sortate sau când adăugați elemente într-o listă deja sortată.
- este foarte ușor de implementat!
complexitate
complexitatea în timp a acestui algoritm, în cel mai rău caz, este pătratică — o(n2). Pe măsură ce n se apropie de infinit, cazul mediu se apropie de cel mai rău caz împărțit la două. Cu toate acestea, deoarece dacă lista dvs. este sortată sau aproape, aceasta poate fi O(n) într-un scenariu cel mai bun caz și, prin urmare, bine adaptată la acel scenariu.
când este rapid
după cum sa menționat mai sus, poate fi rapid în anumite circumstanțe. Luați în considerare matricea , atunci când utilizați un algoritm precum merge sort, ar trebui totuși Să împărțim toate elementele și apoi să le îmbinați înapoi. Cu insertion sort trebuie doar să verificăm dacă sunt în ordinea corectă ‘sortată până acum’, apoi le schimbăm pe toate cu un index pentru 1.
deoarece sortarea inserției este un Sortare adaptivă, îl face și un ‘algoritm online’, ceea ce înseamnă că putem începe sortarea înainte de a obține toate elementele și apoi să îmbinăm listele odată ce sortarea parțială s-a finalizat.
pseudocod
function insertionSort(array)
Loop through array
Create temp var for current element
Create var and set equal to previous element's index
Loop backwards while index >= 0 and current element > temp var
Set next element equal to current element
Set next element equal to temp
Cod
următorul? Merge sortare. Unul dintre cei mai folosiți algoritmi de sortare din browserele de astăzi.
