7.2.1 直接插入排序

插入排序是一种简单直观的排序方法，其基本思想在于每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列，直到全部记录插入完成。

直接插入排序是一种最简单也最直观的插入排序算法。假设在排序过程中，待排序表L[1...n]在某次排序过程的某个时刻状态如下：

为了实现将元素L(i)插入到已有序的子序列L[1...i-1]中,我们需要执行以下操作（为避免混淆，下面用“L[]”表示一个表，而用“L()”表示一个元素）： 1）查找出L(i)在L[1...i-1]中的插入位置k。

2）将L[k...i-1]中所有元素全部后移一个位置。

3）将L(i)复制到L(k)。

为了实现对L[1...n]的排序，可以将L(2)~L(n)一次插入到前面已经排好序的子序列中，初始假定L[1]是一个已经排好序的子序列。上述操作执行n-1次就能得到一个有序的表。插入排序在实现上通常采用就地排序（空间复杂度为O(1)）,因而在从后向前的比较过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。

代码：

void InsertSort(ElemType A[],int n){
     int i,j;
     for(i=2;i<=n;i++){//依次将A[2]~A[n]插入到前面已排序序列
         if(A[i].key<A[i-1].key){//若A[i]的关键字小于其前驱，需要将A[i]插入有序表
            A[0]=A[i];//复制为哨兵,A[0]不存放元素
            for(j=i-1;A[0].key<A[j].key;j--){//从后往前查找待插入位置
                 A[j+1]=A[j];//向后挪位
            }
            A[j+1]=A[0];//复制到插入位置
         }
     }
}

空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1);

时间效率：在排序过程中，向有序子表中逐个地插入元素的操作进行了n-1趟，每趟操作都分为比较关键字和移动元素，而比较次数和移动次数取决于待排序表的初始状态。

在最好情况下，表中元素已经有序，此时每插入一个元素，都只需要比较一次而不用移动元素,因而时间复杂度为O(n).

在最坏情况下，表中元素顺序刚好与排序结果中元素相反(逆序)时，总的比较次数达到最大，为1+2+···+n-1，总的移动次数也达到最大，为1+2+···+n-1.

平均情况下，考虑待排序表中元素是随机的，此时可以取上述最好与最坏情况下的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数约为n^2/4

由此，直接插入排序的时间复杂度为O(n^2)。虽然折半插入排序算法的时间复杂度也有O(n^2)，但对于数据量比较小的排序表，折半插入往往能表现出很好的性能。

稳定性：由于每次插入元素时总是从后往前先比较再移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。

适用性：直接插入排序算法适用于顺序存储和链式存储的线性表。当为链式存储时，可以从前往后查找指定元素的位置。注意：大部分排序算法都仅适用顺序存储的线性表。