算法系列： 10大常见排序算法（3）插入排序

一句

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据

算法介绍

插入排序最好的示例是扑克牌，很多书都以抓扑克牌的过程为例子讲述插入的排序过程。 现在你需要将手牌从左到右按小到大排序。 从最左边开始排序，最左边1张牌是红桃6，显然对于1张牌而言可以看作是已经排好序（有序）的。

现在看第2张牌。 第2张牌和(已经排好序的)第1张比较, 插入到正确的位置

接下来看第3张牌。 第3张牌红桃3依次与左边的牌比较，找到正确的位置插入

	接下来看第4张牌。 第4张牌红桃8依次与左边的牌比较，找到正确的位置插入
	接下来看最后一张牌。 最后一张牌红桃A依次与左边的牌比较，找到正确的位置插入。 到这里，排序大功告成～

动画演示

（from Wikipedia)

算法核心思想

算法实现

一句

没代码的算法都是耍流氓

显然我们需要一个变量i来记录每次扫描未排序部分的开头位置。

问题终于来了。。。

答案是A。 交换2个变量值的代码前面已经见过，就不介绍了。

和选择排序法的比较

插入排序法和选择排序法接近。在选择排序法中，经过k次扫描（整个）数组，最初的k个元素完成排序。

 想一想：

再想一想

不过插入排序法和选择排序法比较，也有自身的代价：

在插入排序法中插入一个元素到已经排好序部分，该部分后右侧元素都需要右移（写操作）；而选择排序法中每次只需要交换一对元素。

当写操作的成本远远高于读操作时，选择排序法更优一些。

一句

 插入排序法比选择排序法优，不过写操作的成本高

算法复杂度

让我们考虑最好情况，最差情况， 和一般情况

最好情况 ：最好情况是数组元素已经排好序啦

During each iteration, the first remaining element of the input is only compared with the right-most element of the sorted subsection of the array.

Comparison/比较次数：Cmin=n-1

Move/移动次数：Mmin=0

最差情况 ： 是排好了，不过方向反了（逆序）

in these cases every iteration of the inner loop will scan and shift the entire sorted subsection 。在最坏情况下，每次都需要走过全部已经排序部分

Comparison/比较次数：Cmax=1+2+3+4+……+n-1=(n-1)n/2

Move/移动次数：Mmax=1+2+3+……+n-1=(n-1)n/2

一般情况 ： 我们用最好和最差的平均值来做粗略估计

我们做个粗略的估算，取最好情况和最坏情况的平均值来表示一般情况。在一般情况下的关键字比较次数和对象移动次数约为 n^2/4。因此，直接插入排序的时间复杂度为 O(n^2)。

一句

插入排序法的时间复杂度为 O(n^2)