插入排序（英語(yǔ)：Insertion Sort）是一種簡(jiǎn)單直觀的排序算法。本文用可視化的方式為您對(duì)其算法機(jī)制進(jìn)行了展示。
算法機(jī)制
插入排序迭代，每次重復(fù)消耗一個(gè)輸入元素，并生成一個(gè)排序的輸出列表。在每次迭代中，插入排序從輸入數(shù)據(jù)中刪除一個(gè)元素，在排序列表中找到它所屬的位置并將其插入那里。它重復(fù)直到?jīng)]有輸入元素剩余。
偽代碼說(shuō)明
一般來(lái)說(shuō)，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：
- 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序
- 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
- 如果該元素（已排序）大于新元素，將該元素移到下一位置
- 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
- 將新元素插入到該位置后
- 重復(fù)步驟2~5
可視化說(shuō)明
適用場(chǎng)景
插入排序不適合對(duì)于數(shù)據(jù)量比較大的排序應(yīng)用。但是，如果需要排序的數(shù)據(jù)量很小，例如，量級(jí)小于千；或者若已知輸入元素大致上按照順序排列，那么插入排序還是一個(gè)不錯(cuò)的選擇。
版權(quán)聲明，本文首發(fā)于 數(shù)字魔盒 https://www.dm2box.com/ 歡迎轉(zhuǎn)載。
