直接插入排序
其他插入排序
希尔排序

直接插入排序

概述

直接插入排序是一种最简单的排序方法，基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

操作

一般情况下，第i趟直接插入排序的操作为：在含有i-1个记录的有序子序列中插入一个记录r[i]，变成一个含有i个有序子序列的记录；和顺序查找类似，为了在查找过程中避免数组下标越界，在r[0]处设置监视哨。在自i-1处向前搜索的过程中，可以同时将元素后移。整个过程进行n-1趟插入。

实现（从小到大）

void InsertSort(int a[],int n){
    for(int i = 1;i<n;++i){
        if(a[i] < a[i-1]){
            int x = a[i];
            int j;
            for(j = i-1;x<a[j] && j>=0;--j){
                a[j+1] = a[j];
            }
            a[j+1] = x;
        }
    }
}

完整测试代码见本人GitHub

复杂度分析

最好情况：基本有序，只需进行外层循环n-1次，复杂度O(n)。
最坏情况：原来逆序，两层for都要执行，此时需要进行的比较共有1/2*n(n-1)次，赋值操作是比较操作的次数减去（n-1）次，（因为n-1次循环中，每一次循环的比较都比赋值多一个，多在最后那一次比较并不带来赋值）。平均来说插入排序算法复杂度为O(n^2)。
因此，在量级小于1e3的情况下可以无压力使用

其他插入排序

目的在于减少直接插入排序中的比较和移动的次数

二分插入排序

直接插入排序的基本操作是在一个有序的子序列中进行查找与插入，故其中的查找工作可以用二分的想法来实现。

void BinaryInsertSort(int a[],int n){
    for(int i = 1;i<n;++i){
        int x = a[i];
        int low = 0,heigh = i-1;
        while(low<=heigh){
            int mid = (low + heigh)/2;
            if(a[mid] > x)    heigh = mid-1;
            else    low = mid+1;
        }
        for(int j = i-1;j>=low;j--)
            a[j+1] = a[j];
        a[low] = x;
    }
}

可见，二分插入排序只减少比较次数，但是移动次数并没有改善。时间复杂度仍为O(n^2)

2-路插入排序

2-路插入排序是在二分插入排序的基础上改进之，目的在于减少元素的移动次数，但需要一个和记录元素的数组一样的辅助空间。

操作

另设一个数组d，首先将a[0]赋值给d[0]，并将d[0]看作是排好序的序列中处于中间位置的元素，然后从a数组中的第二个元素起，依次插入到d数组中，如果a[i] < d[0]，则将a[i]插入到d[0]之前的有序列表中，否则插入到d[0]之后的有序列表中，可以将d看成一个循环向量，并设两个指针first和final分别指示排序过程中得到的最小的元素和最大的元素。

实现

1	//现在较菜，后期更新

复杂度

2-路排序中的元素移动次数约为n^2/8，并且，当d[0]是最小或者最大元素时，2-路插入排序将失去其优越性。

希尔排序

概述

希尔排序又称缩小增量排序，它也是属于插入排序的方法，但在时间效率上较前几种插入排序有较大改进

操作

先将整个待排序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体进行一次直接插入排序

初始关键字如第一行所示，首先将该序列划分为5个子序列，{R0,R5},{R1,R6}…，2——6行，每个子序列中进行直接插入排序，得到第一趟排序结果，然后再将序列划分为增量为3的三个子序列，再进行直接插入排序，得到第二趟排序结果，最后进行直接插入排序，得到最终结果。

实现

void ShellInsertSort(int a[],int dk,int n){
    for(int i = dk;i<n;i+=dk){
        if(a[i]<a[i-dk]){
            int x = a[i];
            for(int j = i-dk;a[j]>x && j>=0;j -= dk){
                a[j+dk] = a[j];
            }
            a[j+dk] = x;
        }
    }
}
void ShellSort(int a[],int n){
    int dk = n/2;
    while(dk>=1){
        ShellInsertSort(a,dk,n);
        dk /=2;
    }
}

完整测试代码见本人GitHub

复杂度

希尔排序的复杂度分析很难，其取决于增量的选取已经元素移动的次数，目前还没有人给出最好的增量选取方案，有取奇数的，有取素数的，需要注意：增量因子中除1 外没有公因子，且最后一个增量因子必须为1，希尔排序是一个不稳定的排序算法

参考资料：
《数据结构——严蔚敏》
《大话数据结构——程杰》
《数据结构——从概念到C实现》