雅乐网

插入排序是一种简单排序。对于少量元素的排序它很有效。

插入排序的工作方式类似于玩扑克牌抓牌时的排序

此图出自算法导论2.1中插入排序插图

开始的时候左手为空，每次从桌子上拿走一张牌并把它插入到左手中正确的位置。可以从右到左依次比较。拿在左手上的牌总是有序的。

c++实现

正确性

下标j表示的是“当前牌”。在for循环的每次迭代开始 a[0]到a[j-1]的子数组构成了当前“左手上排序好的牌”。它总是有序的。我们把它称为循环不变式。

循环不变式可以用来证明算法的正确性。主要性质有

1.初始化：循环的第一次迭代之前，它为真。

2.保持：如果某次迭代之前它为真，那么下次迭代之前它仍然为真。

3.终止： 循环终止时，不变式帮助我们证明正确性。

下面看看插入排序

在算法执行的过程中，a[0]到a[i-1]始终是有序的。

1.初始化：在第一次迭代时，i等于1，a[o]到a[i-1]只包含a[0]，是有序的。这表明第一次迭代之前循环不变式成立。

2.保持：第8行的for循环体将a[i]插入到合适的位置，以使a[0]到a[i]有序。

3.终止： for循环终止的时候i = n 。因此a[0]到a[n-1]的数组已经有序。

复杂度

在最糟糕的情况下，也就是序列逆序排列时，对于n-1个数中第x个数，每次将该数插入时将引起x-1次数组移动（这里不计算比较时间）,求和得到 n(n-1)/2，很明显时间复杂度为O(n²)。

在已经排好序的情况下，时间复杂度为O(n)。