插入排序（英语：Insertion Sort）是一种简略直观的排序算法。本文用可视化的形式为您对其算法机制进行了展现。

算法机制

插入排序迭代，每次反复耗费一个输出元素，并生成一个排序的输入列表。在每次迭代中，插入排序从输出数据中删除一个元素，在排序列表中找到它所属的地位并将其插入那里。它反复直到没有输出元素残余。

伪代码阐明

一般来说，插入排序都采纳 in-place 在数组上实现。具体算法形容如下：

• 从第一个元素开始，该元素能够认为曾经被排序
• 取出下一个元素，在曾经排序的元素序列中从后向前扫描
• 如果该元素（已排序）大于新元素，将该元素移到下一地位
• 反复步骤 3，直到找到已排序的元素小于或者等于新元素的地位
• 将新元素插入到该地位后
• 反复步骤 2~5

可视化阐明

18na5tww41yb7zl53sm0.gif

实用场景

插入排序不适宜对于数据量比拟大的排序利用。然而，如果须要排序的数据量很小，例如，量级小于千；或者若已知输出元素大抵上依照顺序排列，那么插入排序还是一个不错的抉择。

版权申明，本文首发于 数字魔盒 https://www.dm2box.com/ 欢送转载。