(62)王道数据结构-插入排序

基本概念

每次将一个待排序的记录按其关键字大小插入到前面已安排好序的子序列中，直到全部记录插入完成。

插入排序在实现上通常采用就地排序[空间复杂度为O(1)]，因而在从后向前的比较过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。

直接插入排序

假设在排序过程中，待排序表L[1…n]在某次排序过程中的某一时刻状态如下:

有序序列L[1…i-1] L(i) 无序序列L[i+i…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)。

代码实现

//直接插入排序
void InsertSort[ElemType A[], int n) {
    int i,j,temp;
    for(i=1; i<=n; i++) { //将各元素插入已排好序的序列中
        if(A[i]<A[i-1])  {//若A[i]关键字小于前驱
            temp=A[i]; //用temp暂存A[i]
            for(j=i-1; j>=0&&<A[j]>temp; --j) { //检查所有前面已排好序的元素
                A[j+1]=A[j];  //所有大于temp的元素都向后挪位
            }
            A[j+1]=temp; //复制到插入位置
        }
    }
}

代码实现(带哨兵)

为了实现对L[1…n]的排序，可以将L(2)~L(n)依次插入到前面已排好序的子序列中，初始假定L[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)
最坏时间复杂度(全部逆序): O(n^2)
平均时间复杂度: O(n^2)

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

适用性: 直接插入排序算法适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。

注意: 大部分排序算法都仅适用于顺序存储的线性表。

折半插入排序

折半插入排序是对插入排序的优化。每趟插入的过程中，都进行了两项工作:
①从前面的子表中查找出待插入元素应该被插入的位置
②给插入位置腾出空间，将待插入元素复制到表中的插入位置

实现思想

1.折半查找找到应插入到位置，仅适用于顺序表
2.一直到low > high时才停止折半查找。当mid所指元素等于当前元素时，应继续令low = mid + 1，以保证稳定性。最终应将当前元素插入到low所指位置(即high + 1)

代码实现

当排序表为顺序存储的线性表时，可以对直接插入排序算法做如下改进：由于是顺序存储的线性表，所以查找有序子表时可以用折半查找来实现。确定待插入位置后，就可统地向后移动元素。

//折半插入排序
void InsertSort(ElemType A[], int n) {
    int i,j,low,high,mid;
    for(i=2; i<=n; i++) {//依次将A[2]~A[n]插入前面的已排序序列 
        A[0]=A[i]; //将A[i]暂存到A[0]
        low=1; 
        high=1; //设置折半查找的范围
        while(low<=high) { //折半查找(默认递增有序)
            mid=(low+high)/2; //取中间点
            if(A[mid].key>A[0].key) {
                high=mid-1; //查找左半子表
            } else {
                low=mid+1; //查找右半子表
            } 
        }
        for(j=i-1; j>=high+1; --j) {
            A[j+1]=A[j]; //统一后移元素，空出插入位置
        }
        A[high+1]=A[0]; //插入操作
    }
}