插入排序

本节中，我们考虑如何用减一技术来对一个数组A[0..n-1]排序。遵循该方法的思路，假设对较小数组A[0..n-2]排序的问题已经解决，也就是一个大小为n-1的有序数组：A[0]≦..≦A[m-2].如何把这个较小规模的解和元素A[n-1]一同考虑，来得到原问题的解呢？就是在这些有序元素中为A[n-1]找到一个合适的位置，然后把它插入到那里。

有3种合理的做法可以达到这个目的，它们各不相同。

第一，从左到右扫描这个有序的子数组，直到遇到第一个大于等于A[n-1]的元素，然后把A[n-1]插在该元素的前面。

第二，从右往左扫描这个有序的字数组，直到遇到第一个小于等于A[n-1]的元素，然后就把A[n-1]插在该数组的后面。

本质上两种做法是相同的，但一般在实践中，第二种方法用得更多一些，因为对于有序和基本有序的数组，它的效率更高一些。这两种算法称为直接插入排序,或者简称插入排序.

第三种做法是使用折半查找为A[n-1]在有序数组中找到一个合适的位置。这种算法被称为折半插入排序.

虽然插入排序基于递归思想，但从底至上地实现这个算法，也就是使用迭代，效率会更高。

下面是这个算法的伪代码。

算法 InsertionSrt(A[0..n-1])
    //用插入排序对给定数组排序
    //输入：n个可排序元素构成的一个数组A[0..n-1]
    //输出：非降序排列的数组A[0..n-1]
    for i<-1 to n-1 do
        v <- A[i]
        j <- i-1
        while j≧0 and A[j] > v do
            A[j+1] <- A[j]
            j <- j-1
        A[j+1] <- v

该算法的键值比较次数依赖于特定的输入。最坏的情况，A[j] > v的执行次数最大，对于每个j＝i－1,…,0，都要执行一次。即最坏输入是一个严格递减的数组，这种谁人的键值比较次数是：

最坏的情况，插入排序和选择排序的键值比较次数是完全一致。

最好的情况，在外部循环的每次迭代中，比较操作A[j] > v只执行一次。即输入数组已经按照升序排列了。因此，对于有序的数组，键值比较次数是

插入排序应用基本有序的文件，对于这样的输入，它保持了它的良好性能。例如，在用快速排序对数组排序的时候，当子数组的规模变得小于某些预定义的值时，（比方说，10个元素），我们可以停止该算法的迭代。此时，整个数组已经基本有序了，我们可以对它应用插入排序来完成接下来的工作。对快速排序做了这种改动之后，一般会减少10%的运行时间。

分析表明，对于随即序列的数组，插入排序的平均比较次数是降序数组的一半，也就是说，

平均性能比最差性能快两倍，以及遇到基本有序的数组时表现出的优异性能，使得插入排序优于选择排序和冒泡排序。另外，它有一种扩展算法，叫做Shell排序，提供了一种更好的算法来对较大的文推荐进行排序。