tento článek je součástí série zahrnující algoritmy řazení v JavaScriptu. Zbytek série najdete zde. Pokud jste novým třídícím algoritmům nebo algoritmům obecně, přečtěte si toto nejprve a získejte pevný základ pro postup vpřed. Dnes budu pokrývat vstupy a výstupy typu vložení. Třídění vložení je složitější, ale o něco užitečnější než třídění bublin. Nejhorší scénář pro to je podobný bubble sort, ale jeho nejlepší případ je vhodný pro časy, kdy jste si jisti, že seznam je téměř seřazen nebo pravděpodobně již seřazen. Pojďme si to představit.
třídění vložení funguje tak, že se podíváte na každý prvek v seznamu (počínaje druhým prvkem) a porovnáte jej s položkou dříve. Pokud je položka před větší, jsou vyměněny. Toto pokračuje, dokud není položka menší, v tomto okamžiku uděláme totéž pro další prvek v seznamu.
řazení vložení není tak špatné.. pokud ji používáte za správných okolností.
- je to rychlejší než většina O (n log n) třídění algoritmů pro malé seznamy.
- je to extrémně efektivní paměť vyžadující pouze o(1) pomocný prostor pro jednu položku, která se přesouvá.
- je stabilní-stejné prvky se zobrazují ve stejném pořadí v řazeném seznamu.
- je to adaptivní-je to rychlé při třídění většinou seřazených seznamů nebo při přidávání položek do již seřazeného seznamu.
- je velmi snadné implementovat!
složitost
časová složitost tohoto algoritmu je v nejhorším případě kvadratická-O (n2). Jak se n blíží nekonečnu, průměrný případ se blíží nejhoršímu případu děleno dvěma. Nicméně, protože pokud je váš seznam seřazen nebo téměř tak, může být O (n)v nejlepším případě, a tak dobře přizpůsoben tomuto scénáři.
když je to rychlé
jak je uvedeno výše, může být za určitých okolností rychlé. Zvažte pole, při použití algoritmu, jako je sloučit třídění, bychom stále museli rozdělit všechny položky a poté je sloučit zpět. S vložením třídění stačí ověřit, že jsou ve správném pořadí „seřazeny tak daleko“, pak je všechny posuneme o jeden index pro 1.
protože insertion sort je adaptivní řazení, dělá to také „online algoritmus“, což znamená, že můžeme začít třídit dříve, než dostaneme všechny položky, a poté sloučit seznamy po dokončení částečného třídění.
pseudokó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
další na řadě? Sloučit třídění. Jeden z nejpoužívanějších algoritmů třídění v prohlížečích dnes.
