1.概念

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

2.性能

空间复杂度：O(1)

时间复杂度

最好：原本有序O(n)
最坏：原本逆序O(n^2)
平均：O(n^2)

稳定性：稳定

3.直接插入排序

顺序查找插入位置，适用于顺序表、链表

算法思想

将0号位置放哨兵：要插入的元素
每次将一个待排序的记录按其关键字插入到前面已排号的序列中

代码

// 直接插入排序
void insertSort(SqList& L)
{
    if (L.length <= 1)
        return;
    // 依次将 2~n 插入到前面已排序的序列
    for (int i = 1; i < L.length; i++)
    {
        // i 小于前驱，将 i 插入有序表
        if (L.data[i] < L.data[i - 1])
        {
            ElemType tmpElem = L.data[i];
            int j = i - 1;
            // 从后往前查找待插入位置
            for (; tmpElem < L.data[j]; j--)
                // 向后移动元素
                L.data[j + 1] = L.data[j];
            // 插入
            L.data[j + 1] = tmpElem;
        }
    }
}

4.折半插入排序

折半查找找到应插入的位置，仅适用于顺序表

算法思想

折半查找

在[low, high]之间找目标关键字，每次检查 mid = (low + high)/2
根据mid所指示元素与目标关键字的大小调整low或high，不断缩小low和high的范围
若low > high，则查找失败

注意

一直到low>high时才停止折半查找。当mid所指元素等于当前元素时，应继续令low=mid+1，以保证“稳定性”。最终应将当前元素插入到low所指的位置，即high+1.

代码

// 折半插入排序
void binInsertSort(SqList& L)
{
    int low, high, mid;
    for (int i = 1; i < L.length; i++)
    {
        ElemType tmpElem = L.data[i];
        // 设置查找范围
        low = 0;
        high = i - 1;
        // 查找
        while (low <= high)
        {
            mid = (low + high) / 2;
            // 查找左半部分
            if (L.data[mid] > tmpElem)
                high = mid - 1;
            // 查找右半部分
            else
                low = mid + 1;
        }
        // 后移元素，空出插入位置
        // 注意范围，low指针指向选中的元素
        for (int j = i - 1; j >= low; j--)
        {
            L.data[j + 1] = L.data[j];
        }
        // 插入
        L.data[low] = tmpElem;
    }
}

5.希尔排序

算法思想

先将排序表分割成若干如L[i, i+d, i+2d, ..., i+kd] 的“特殊”子表，对各个子表进行直接插入排序。
缩小增量d，重复上述过程，直到d=1为止。

性能

空间复杂度：O(1)
时间复杂度：未知，但优于直接插入排序
稳定性：不稳定
适应性：仅可适用于顺序表

代码

// 希尔排序
void shellSort(SqList& L)
{
    // 步长
    for (int dk = L.length / 2; dk >= 1; dk = dk / 2)
    {
        for (int i = dk + 1; i < L.length; i++)
        {
            if (L.data[i] < L.data[i - dk])
            {
                // 将i插入有序增量子表
                ElemType tmpElem = L.data[i];
                int j = i - dk;
                // 元素后移
                for(; j > 0 && tmpElem < L.data[j]; j -= dk)
                {
                    L.data[j + dk] = L.data[j];
                }
                // 插入
                L.data[j + dk] = tmpElem;
            }
        }
    }
}