时间复杂度O(n2)，最好情况O(n)，最坏情况O(n2)，稳定。（同冒泡）
- 是一种简单直观的排序算法。适用于量级小于千，或者若已知输入元素大致上按照顺序排列。
- 插入排序不适合对于数据量比较大的排序应用。
工作原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素（第二个元素）作为目标元素，在已经排序的元素序列中从后向前扫描
- 如果当前元素（扫描到的元素）大于目标元素，将当前元素与目标元素交换
- 重复步骤3，直到找到目标元素的位置（当前元素小余或等于目标元素）
- 重复步骤2-4
使用数组结构的话，没比较一次且满足插入条件的话就需要交换一次，如果使用链表结构（只用记录后继，但同时需要维护下标；记录后继和前驱，无需维护下标）的话，只需记录位置，最后插入即可，无需插入多次。
先对数组前两个元素进行排序，之后将第三个元素与前两个比较，按排序规则插入正确的位置，之后将第四个元素与前三个，比较插入正确的位置，以此类推直至最后一个元素
如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找插入排序。
实现类为：InsertionSort
image.png
代码已上传 GitHub ，可以在 这里 找到
网友评论