插入排序（英语：Insertion Sort）是一种简单直观的排序算法。本文用可视化的方式为您对其算法机制进行了展示。
算法机制
插入排序迭代，每次重复消耗一个输入元素，并生成一个排序的输出列表。在每次迭代中，插入排序从输入数据中删除一个元素，在排序列表中找到它所属的位置并将其插入那里。它重复直到没有输入元素剩余。
伪代码说明
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
可视化说明
适用场景
插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千；或者若已知输入元素大致上按照顺序排列，那么插入排序还是一个不错的选择。
版权声明，本文首发于 数字魔盒 https://www.dm2box.com/ 欢迎转载。
