插入排序（一）

基本概念

一种简单直观的排序方法，基本思想是 每一次将一个待排序的元素，按照大小插入到前面已排好序的子序列中去，知道全部元素排序完成，这样的操作称为插入排序，包括直接插入排序和希尔排序等。

直接插入排序（Straight Insertion Sort）

基本思想

将待排序列分为无序序列和有序序列两部分，然后依次将无序区的第一个元素按大小顺序插入到有序区中去，每次比较插入，无序区减1，有序区加1，最终将所有无序区元素都移动到有序区完成排序。

具体地，先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

要点：设立哨兵，作为临时存储和判断数组边界之用。

代码实现

void InsertSort(int L[], int n)
{
    int i, j;
    for (i = 2; i <=n; ++i) // 起始首位置1（0号为哨兵）为有序部分，剩下n-1为待排序部分
    {
        L[0] = L[i]; // L[0]既为哨兵，又起到临时存储作用
        // 因为L[0]位置即为当前待插入元素，因此当判断到L[0]时，循环必将结束，
        // 不必考虑数组越界问题，即为哨兵作用
        for (j = i-1; L[j] > L[0]; --j) // 在有序部分中为L[i]找位置
            L[j+1] = L[j]; // 元素后移
        L[j+1] = L[0]; // 第j位时退出循环，此时应插入到j+1，原j+1位已空出
    }
}

归纳分析

1. 稳定排序（stable sort）

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是 稳定排序 。

2. 空间复杂度（in-place 原地算法，O(1)）

需要一个辅助空间暂存元素，直接插入排序的空间复杂度为 O(1)。

3. 时间复杂度

比较和移动操作一块进行；

最好情况下，时间复杂度为 O(n)，此时待排序列原本有序。

最坏情况下，时间复杂度为 O(n²)，此时待排序列刚好逆序。

考虑哨兵的比较，比较次数为 Σi= (n+2)(n-1)/2，（i = {2,…,n}）
不考虑哨兵的比较，比较次数为 Σi - (n-1)= n(n-1)/2, i = {2,…,n}，

移动次数为 Σ(i+1)= (n+4)(n-1)/2，（i = {2,…,n}）。

插入排序的时间复杂度与逆序对的数量保持一致，当数组倒序时，逆序对的个数为n(n-1)/2，因此插入排序复杂度为O(n²)。

平均情况下，直接插入排序的时间复杂度为 O(n²)。

4. 初态影响

由3中分析，时间复杂度 与初始状态有关

5. 过程特征

一趟排序不能确定一个元素的最终位置，但会产生局部有序的有序子序列。

局部有序：有序序列中的元素与无序序列中的元素大小关系未知。

根据插入排序的原理，插入排序会产生有序子序列，但只是*局部有序；

插入排序不到最后一趟排序，每个元素都有可能不在其最终的位置上，一个极端的例子是，最后一趟排序是将最后一个元素插入到有序序列的第一个位置上，这样一来，在最后一趟排序之前，所有元素都不在其最终位置上。

6. 适用性

插入排序比较适合用于“基本有序”的序列和“数据量不大（不大于50）”的序列，不过因为直接插入排序移动操作比较多，所以不太适合元素本身信息量较大的情况，可用冒泡排序。

算法证明（来自算法导论）

循环不变式：在每次循环开始前，A[1…i-1]包含了原来的A[1…i-1]的元素，并且已排序。

初始：i=2，A[1…1]已排序，成立。
保持：在迭代开始前，A[1…i-1]已排序，而循环体的目的是将A[i]插入A[1…i-1]中，使得A[1…i]排序，因此在下一轮迭代开 始前，i++，因此现在A[1…i-1]排好序了，因此保持循环不变式。
终止：最后i=n+1，并且A[1…n]已排序，而A[1…n]就是整个数组，因此证毕。

其他问题

• 代码 7-8 行能否用用二分法实现？

不能。因为第 7-8 行并不是单纯的线性查找，而是还要移出一个空位让A[i]插入，即，比较和移动操作是一起的，因此就算二分查找用 O(logn) 查到了插入的位置，但还是要用 O(n) 的时间移出一个空位，这就是折半插入排序。

• 快速排序（不使用随机化）是否一定比插入排序快？

不一定。最好情况下，待排序列原本有序，插入排序需要 O(n) 时间，而快速排序需要 O(n²) 时间。

折半插入排序（Binary Insertion Sort）

基本思想

之前的直接插入排序是一边比较一边移动，现在将比较和移动操作分离，先用折半查找得到待插入位置，然后统一移动；

因此，折半插入排序仅仅减少了比较次数，时间复杂度为 O(nlogn)，其与初始状态无关，仅取决于元素个数 n；

但移动次数不变，时间复杂度为 O(n²)，其仍然与初始状态有关，因此，时间复杂度仍为 O(n²)

代码实现

void BInsertSort(int L[], int n)
{
    int i, j, low, high, mid;
    for (i = 2; i <= n; ++i)
    {
        low = 1; high = i-1;
        while(low <= high) // 查找，循环中满足L[low]<=L[0]<=L[high]
        {
            mid = (low + high)/2;
            if (L[i] < L[mid]) high = mid - 1; // 左半
            else low = mid +1; // 右半）
        } // 退出时low-high=1，应当插在high+1的位置
        L[0] = L[i];
        for (j = i; j > high+1; --j) // 移动
            L[j] = L[j-1];
        L[high+1] = L[0];
    }
}

归纳分析

1. 稳定排序（stable sort）

仍是插入排序，仅在比较查找时进行了折半查找优化，移动操作不变，因此仍是 稳定排序 。

2. 空间复杂度（in-place 原地算法，O(1)）

需要一个辅助空间暂存元素，折半插入排序的空间复杂度为 O(1)。

3. 时间复杂度

比较和移动操作分离；

减少了比较操作的次数，移动操作次数不变；

平均情况下，折半插入排序的时间复杂度为 O(n²)。

4. 初态影响

比较次数减少，时间复杂度为 O(nlogn)，与初始状态无关；
移动次数不变，时间复杂度为 O(n²)，与初始状态有关。

5. 适用性

折半插入仅针对顺序存储优化，只适用于顺序存储 的线性表。