denne artikel er en del af en serie, der dækker sorteringsalgoritmer i JavaScript. Du kan finde resten af serien her. Hvis du er ny med sorteringsalgoritmer eller algoritmer generelt, skal du læse dette først for at få et solidt fundament for at komme videre. I dag vil jeg være at dække ins og outs af indsættelse slags. Indsætningssortering er mere kompleks, men lidt mere nyttig end boblesortering. Det værste tilfælde for det ligner bubble sort, men det bedste tilfælde gør det velegnet til tidspunkter, hvor du er ret sikker på, at en liste næsten er sorteret eller sandsynligvis allerede sorteret. Lad os få det store billede.
Indsætningssortering fungerer ved at se på hvert element i en liste (startende med det andet element) og sammenligne det med elementet før. Hvis varen før er større, byttes de. Dette fortsætter, indtil varen er mindre, på hvilket tidspunkt vi gør det samme for det næste element på listen.
Indsætningssortering er ikke så slemt.. så længe du bruger det under de rigtige omstændigheder.
- det er hurtigere end de fleste o(n log n) sorteringsalgoritmer til små lister.
- det er ekstremt hukommelseseffektivt, der kun kræver o(1) ekstra plads til det enkelte element, der flyttes.
- det er stabilt — lige elementer vises i samme rækkefølge i den sorterede liste.
- det er adaptivt — det er hurtigt, når du sorterer mest sorterede lister, eller når du tilføjer elementer til en allerede sorteret liste.
- det er meget nemt at implementere!
kompleksitet
tidskompleksiteten af denne algoritme er i værste fald kvadratisk — o(n2). Når n nærmer sig uendelighed, nærmer den gennemsnitlige sag det værste tilfælde divideret med to. Men da hvis din liste er sorteret eller næsten så, kan den være O(n) i bedste fald og dermed godt tilpasset dette scenario.
når det er hurtigt
som nævnt ovenfor kan det være hurtigt under visse omstændigheder. Overvej arrayet, når vi bruger en algoritme som Flet sortering, skal vi stadig opdele alle elementerne og derefter flette dem op igen. Med indsætningssortering skal vi bare kontrollere, at det er i den korrekte ‘sorteret indtil videre’ rækkefølge, så skifter vi dem alle op et indeks for 1.
fordi indsætningssortering er en adaptiv sortering, gør den det også til en ‘online algoritme’, hvilket betyder, at vi kan begynde at sortere, før vi får alle elementerne og derefter flette listerne, når den delvise sortering er afsluttet.
pseudokode
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
kode
næste op? Flet sort. En af de mest anvendte sorteringsalgoritmer i dag.
