本文共 848 字，大约阅读时间需要 2 分钟。
1. 思路
插入排序基于一种简单的思路:把数组分为左右两个部分，左侧为有序数组，右侧为无序数组，把右侧的无序数组，一个一个的插入到左侧的有序数组中，从而步步为营的完成排序。排序过程如下：
① 第2位与第1位比较，如果比第一位小就换位置
② 第3位与第2位比，如果比第2位小就换位置，第2位再与第1位比较，如果比第1位小就换位置.
…….
③ 直到最后一位
2. 代码相关部分
① 插入排序代码段
② 运行过程
绿色是以完成排序，红色为本次排序交换部分，黑色为无操作部分
3.时间复杂度
我们不妨输入两组性质完全相反的数组来观察执行过程。
a. 正序序列[0,1,2,3,4,5,6,7,8,9]
执行过程图
我们可以看到，在有序系列中，只有红色对角线执行了比较操作，没有任何交换操作。由此，可以得出，对于任意有序序列N，比较次数为N-1.
b. 倒序序列[9,8,7,6,5,4,3,2,1,0]
执行过程如下
第1行，比较1次 交换1次
第2行，比较两次，交换两次
……
第9行比较9次，交换9次
把10换成任意长度N 比较次数 1+2+…+N-1= N2/2.
交换次数同样为N2/2.
由此，我们可以得出，正序序列的时间复杂度为O(N)，倒序序列的时间复杂度为O(N2)。所以插入序列的时间复杂度为O(N2)
4.特性与思考
不同于，插入排序依赖输入的特性，输入序列顺序性越好，排序效率越高。
有关性能优化的思考：
① 预处理。因为插入排序对有序序列有很好的性能优势，那么我们可不可以先将数组处理一下，处理成大致有序的，然后再进行插入排序呢？
② 交换次数优化。考量如下代码段
每一步，如果右侧的数据小于左侧的数据，就需要进行交换,这会导致很多交换实际上是无效的，实际上整个循环交换一次就够了。
③ 比较次数优化。承接2，能否在比较次数上做些优化呢？我们能够看到，插入算法的比较是线性的。因为我们要插入的左侧部分是有序的，所以可以尝试着用二分法查找来进行优化，这样线性比较就变成了指数比较。