插入排序

插入排序是一种简单直观的排序方法，其基本思想是每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成。由插入排序的思想可以引申出三个重要的排序算法：直接插入排序、折半插入排序和希尔排序。

直接插入排序

根据上面的插入排序思想，不难得出一种最简单也最直观的直接插入排序算法。假设在排序过程中，待排序表L[l...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[l...n]的排序，可以将L(2)~L(n)依次插入前面已排好序的子序列，初始L[1]可以视为是一个已排好序的子序列。上述操作执行 $n-1$ 次就能得到一个有序的表。插入排序在实现上通常采用就地排序（空间复杂度为 $O(1)$ ），因而在从后向前的比较过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。

下面是直接插入排序的代码，其中再次用到了我们前面提到的“哨兵”（作用相同）。

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

假定初始序列为49, 38, 65, 97, 76, 13, 27，初始时49可以视为一个已排好序的子序列， 按照上述算法进行直接插入排序的过程如下图所示，括号内是已排好序的子序列。

直接插入排序算法的性能分析如下：

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

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

• 在最好情况下，表中元素已经有序，此时每插入一个元素，都只需比较一次而不用移动元素，因而时间复杂度为 $O(n)$ 。
• 在最坏情况下，表中元素顺序刚好与排序结果中的元素顺序相反（逆序），总的比较次数达到最大，为 ${\sum }_{i=2}^{n}i$ ，总的移动次数也达到最大，为 ${\sum }_{i=2}^n(i+1)$
• 平均情况下，考虑待排序表中元素是随机的，此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数均约为 $n^2/4$ 。

因此，直接插入排序算法的时间复杂度为 $O(n^2)$ 。

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

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

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

折半插入排序

从直接插入排序算法中，不难看出每趟插入的过程中都进行了两项工作：
1）从前面的有序子表中查找出待插入元素应该被插入的位置
2）给插入位置腾出空间，将待插入元素复制到表中的插入位置
注意到在该算法中，总是边比较边移动元素。下面将比较和移动操作分离，即先折半查找出元素的待插入位置，然后统一地移动待插入位置之后的所有元素。当排序表为顺序表时， 可以对直接插入排序算法做如下改进：由于是顺序存储的线性表，所以查找有序子表时可以用折半查找来实现。确定待插入位置后，就可统一地向后移动元素。算法代码如下:

void InsertSort(int *A, int n) {
    int i, k, low, high, mid;
    for (i = 2; i < n; i++)     //依次将A[2]〜A[n]插入前面已排序序列
        if (A[i] < A[i - 1]) {  //若A[i]关键码小于其前驱，将A[i]插入有序表
            A[0] = A[i];        //复制为哨兵，A[0]不存放元素
            low = 1;
            high = i - 1;       //设置折半查找的范围
            while (low <= high) {   //折半査找(默认递增有序)
                mid = (low + high) / 2;
                if (A[mid] > A[0])
                    high = mid - 1; //查找左半子表
                else
                    low = mid + 1;  //査找右半子表
            }

            for (k = i - 1; k >= high + 1; k--)
                A[k + 1] = A[k];    //统一后移元素，空出插入位置
            A[high + 1] = A[0];     //插入操作
        }
}

从上述算法中，不难看出折半插入排序仅减少了比较元素的次数，约为 $O(n{\log }_{2}n)$ ，该比较次数与待排序表的初始状态无关，仅取决于表中的元素个数 $n$ ；而元素的移动次数并未改变，它依赖于待排序表的初始状态。因此，折半插入排序的时间复杂度仍为 $O(n^2)$ ，但对于数据量不很大的排序表，折半插入排序往往能表现出很好的性能。折半插入排序是一种稳定的排序方法。

希尔排序

从前面的分析可知，直接插入排序算法的时间复杂度为 $O(n^2)$ ，但若待排序列为“正序”时，其时间复杂度可提高至 $O(n)$ ，由此可见它更适用于基本有序的排序表和数据量不大的排序表。希尔排序正是基于这两点分析对直接插入排序进行改进而得来的，又称缩小增量排序。

希尔排序的基本思想是：先将待排序表分割成若干形如 $L[i,i+d,i+2d,\cdots ,i+kd]$ 的"特殊" 子表，即把相隔某个“增量”的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。

希尔排序的过程如下：先取一个小于 $n$ 的步长 $d_1$ ，把表中的全部记录分成 $d_1$ 组，所有距离为 $d_1$ 的倍数的记录放在同一组，在各组内进行直接插入排序；然后取第二个步长 $d_2<d_1$ ，重复上述过程，直到所取到的 $d_t=1$ ，即所有记录已放在同一组中，再进行直接插入排序，由于此时已经具有较好的局部有序性，故可以很快得到最终结果。到目前为止，尚未求得一个最好的增量序列。以关键字序列[49, 38, 65, 97, 76, 13, 27, 49, 55, 04]为例，第一趟取增量 $d_1=5$ ，将该序列分成5个子序列，即图中第2行至第6行，分别对各子序列进行直接插入排序，结果如第7行所示；第二趟取增量 $d_2=3$ ，分别对3个子序列进行直接插入排序，结果如第11行所示；最后对整个序列进行一趟直接插入排序，整个排序过程如下图所示。

希尔排序算法的代码如下：

void ShellSort(int *A, int n) {
    // A[0]只是暂存单元，不是哨兵，当k<=0时，插入位置已找到
    int i, k, dk;
    for (dk = n / 2; dk >= 1; dk = dk / 2)  //步长变化
        for (i = dk + 1; i < n; i++)
            if (A[i] < A[i - dk]) {     //需将A[i]插入有序增量子表
                A[0] = A[i];            //暂存在A[0]
                for (k = i - dk; k > 0 && A[0] < A[k]; k -= dk)
                    A[k + dk] = A[k];   //记录后移，查找插入的位置
                A[k + dk] = A[0];       //插入
            }
}

希尔排序算法的性能分析如下：

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

时间效率：由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题，所以其时间复杂度分析比较困难。当 $n$ 在某个特定范围时，希尔排序的时间复杂度约为 $O(n^{1.3})$ 。在最坏情况下希尔排序的时间复杂度为 $O(n^2)$ 。

稳定性：当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。例如，在上面例子中49的相对次序已发生了变化。

适用性：希尔排序算法仅适用于线性表为顺序存储的情况。