ez a cikk egy sorozat része, amely a JavaScript rendezési algoritmusait tartalmazza. A sorozat többi részét itt találod. Ha még nem ismeri az algoritmusok rendezését, vagy általában az algoritmusokat, először olvassa el ezt, hogy szilárd alapot kapjon a továbblépéshez. Ma fogok, amely a csínját-bínját beillesztés sort. A beillesztés rendezése összetettebb, de egy kicsit hasznosabb, mint a buborék rendezése. A legrosszabb eset hasonló a bubble sort-hez, de a legjobb eset alkalmassá teszi olyan esetekre, amikor biztos benne, hogy egy lista szinte rendezve vagy valószínűleg már rendezve van. Nézzük a nagy képet.
a beszúrási rendezés úgy működik, hogy a lista minden elemét megnézi (a második elemmel kezdve), és összehasonlítja az előző elemmel. Ha az előző elem nagyobb, akkor cserélik őket. Ez addig folytatódik, amíg az elem kisebb lesz, ekkor ugyanezt tesszük a lista következő elemével is.
a beszúrási rendezés nem olyan rossz.. mindaddig, amíg a megfelelő körülmények között használja.
- gyorsabb, mint a legtöbb o(n log n) rendezési algoritmus kis listákhoz.
- ez rendkívül memória hatékony igénylő csak O (1) kiegészítő helyet az egyetlen elem, hogy mozog.
- stabil — az egyenlő elemek ugyanabban a sorrendben jelennek meg a rendezett listában.
- adaptív — gyors, ha többnyire rendezett listákat rendez, vagy ha elemeket ad hozzá egy már rendezett listához.
- nagyon könnyen megvalósítható!
komplexitás
ennek az algoritmusnak az időbonyolultsága a legrosszabb esetben másodfokú — O(n2). Ahogy n közeledik a végtelenhez, az átlagos eset megközelíti a legrosszabb esetet osztva kettővel. Mivel azonban a lista rendezve van, vagy majdnem így van, a legjobb esetben O(n) lehet, így jól alkalmazkodik ehhez a forgatókönyvhöz.
ha gyors
mint fent említettük, bizonyos körülmények között gyors lehet. Fontolja meg a tömböt , ha olyan algoritmust használ, mint az egyesítés rendezés, akkor is fel kell osztanunk az összes elemet, majd össze kell egyesítenünk őket. A beszúrási rendezéssel csak ellenőriznünk kell, hogy a helyes sorrendben vannak-e, majd mindegyiket egy indexre toljuk 1-re.
mivel a beszúrási rendezés adaptív rendezés, online algoritmussá is teszi, ami azt jelenti, hogy elkezdhetjük a rendezést, mielőtt megkapnánk az összes elemet, majd egyesíthetjük a listákat, miután a részleges rendezés befejeződött.
pszeudokód
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
Kód
következő? Egyesítés rendezés. A böngészők egyik legszélesebb körben használt rendezési algoritmusa.
