tämä artikkeli on osa sarjaa, joka kattaa lajitella algoritmeja JavaScript. Loput sarjasta löydät täältä. Jos lajittelualgoritmit tai algoritmit yleensä ovat sinulle uusia, lue tämä ensin saadaksesi vankan pohjan eteenpäin etenemiselle. Tänään hoidan insertion sortin läpikotaisin. Insertion sort on monimutkaisempi, mutta hieman hyödyllisempi kuin bubble sort. Pahimmassa tapauksessa se on samanlainen kuin bubble sort n, mutta sen parhaassa tapauksessa se sopii aikoja, jolloin olet melko varma luettelo lähes lajiteltu tai todennäköisesti jo lajiteltu. Otetaan kokonaiskuva.
Lisäyslajittelu toimii tarkastelemalla jokaista alkuainetta luettelossa (alkaen toisesta alkuaineesta) ja vertaamalla sitä edeltävään alkuaineeseen. Jos kohde ennen on suurempi, ne vaihdetaan. Tämä jatkuu, kunnes kohde on pienempi, jolloin teemme saman seuraavan osan luettelossa.
Insertion sort isn ’ t all that bad.. kunhan käytät sitä oikeissa olosuhteissa.
- se on nopeampi kuin useimmat o (n log n) – lajittelualgoritmit pienille listoille.
- se on erittäin muistitehokas vaatien vain O(1) aputilaa yksittäiselle siirrettävälle esineelle.
- sen stabiili-samanarvoiset alkuaineet esiintyvät samassa järjestyksessä lajitellussa luettelossa.
- se on mukautuva-se on nopea, kun lajittelee enimmäkseen lajiteltuja luetteloita tai lisää kohteita jo lajiteltuun luetteloon.
- se on erittäin helppo toteuttaa!
monimutkaisuus
tämän algoritmin ajallinen monimutkaisuus on pahimmassa tapauksessa kvadraattinen — O(n2). Kun n lähestyy ääretöntä, keskimääräinen tapaus lähestyy pahinta tapausta jaettuna kahdella. Kuitenkin koska jos luettelo on lajiteltu tai lähes niin, se voi olla O(n) parhaassa tapauksessa ja siten hyvin sovitettu kyseiseen skenaarioon.
kun se on nopea
kuten edellä mainittiin, se voi olla nopea tietyissä olosuhteissa. Harkitse array, kun käytät algoritmia kuten merge lajitella meidän vielä jakaa kaikki kohteet ja sitten yhdistää ne takaisin ylös. Kanssa lisäys lajitella meidän tarvitsee vain tarkistaa, että ovat oikeassa ’lajiteltu toistaiseksi’ järjestyksessä, sitten siirrämme kaikki ne ylös yhden indeksin 1.
koska insertion sort on adaptiivinen lajittelu, se tekee siitä myös ”online-algoritmin”, mikä tarkoittaa, että voimme aloittaa lajittelun ennen kuin saamme kaikki kohteet ja yhdistää luettelot sitten, kun osittainen lajittelu on suoritettu.
pseudokoodi
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
koodi
seuraavaksi? Yhdistä Lajittele. Yksi yleisimmin käytetty lajittelualgoritmeja selaimet tänään.
