插入排序

1. 直接插入

基本思路：不断地把 指针 i 指向的关键字插入到前面的有序序列，然后 i 指向无序序列的第一个关键字

1. 指针 i 指向第一个关键字
2. 指针往后移一位
3. 指针指向的关键字插入到 i 前面有序的序列中
   • 如果 a[i] > a[i + 1]，则不用修改顺序
   • 如果 a[i] < a[i + 1]，则找到适合的位置插入，把所有后面的关键字往后移动一位
4. 指针 i 指向下一位

void InsertSort(ElemType a[], int n)
{
    int i,j;
    for (i = 2; i <= n; i++)
    {
        if(a[i].key < a[i - 1].key) // 如果 i 大于 i - 1 的关键字，可以直接插入
        {
            a[0] = a[i];
            for (j = i - 1;a[0].key < a[j].key; j--) 
            {
                //在循环中，一边对比，一边把关键字后移
                //满足条件则停止后移
                a[j + 1] = a[j];
            }
            a[j + 1] = a[0];
        }
    }
}

• 空间效率：O(n)
• 时间效率
  • 最好:O(n)，进行n - 1次插入。最好情况，是序列本来就是有序的，因此，每次只需要把第 i 个关键字插入到前面的有序序列中就好了，不需查找插入位置
  • 最坏:O(n²)。最坏情况，完全逆序，每次要和前面所有的关键字作对比，把前面每个关键字后移。因此操作次数是，∑ ^{n - 1} (i - 1)² i = 1，2，3.....直到n - 1
  • 平均情况: 取最好，最坏情况的平均数，此时总的比较次数和总的移动次数均为 n²/4

2. 折半插入

可见，插入排序都存在一个过程，先找到插入的位置（查找），插入。
直接插入的查找方式简单粗暴，直接逐一比对，直到找到合适的位置。折半插入的基本思路与直接插入一致，但是查找方式不同，是利用折半查找。
因此，时间复杂度，改变的只是查找插入位置的时间，从n次变成 log₂n

low = 1;high = i -1;
while(low < high)
{
    mid = (low + high) / 2;
    if(a[mid].key < a[0].key)
        low = mid + 1;
    else
        high = mid - 1; 
}

3. 希尔排序

• 基本思路：多次对整个序列分成多个不同，可能相互重叠的子序列进行排序，使得整个序列顺序不断接近顺序。
• 分组依据，设置初始间隔dk，不断地改变dk，并每次根据间隔dk去访问整个序列，形成子序列，并排序。
• 每一趟子序列的排序使得整个序列越来越接近顺序，同时每次减少dk使得子序列不断变大，最终dk = 1的时候，所得子序列便是整个序列。

void ShellSort(ElemType a[], int n)
{
    for (dk = n/2; dk >= 1; dk = dk / 2)//不断使得dk变小，初始dk以及变小方式都是没有固定的
    {
        
        for (i = dk + 1; i <= n; i += dk)//对以dk划分的子序列进行直接插入排序
        {
            if (a[i].key < a[i - dk].key)
                a[0] = a[i];
                for (j = i -dk; j > 0 && a[0].key < a[j].key; j -= dk)
                    a[j + dk] = a[j];
                a[j + dk] = a[0];
        }
     }
}

• 空间效率:O(1)
• 时间效率:依赖于增量序列的函数。当n在某个特定的范围是，O(n^1.3)，最坏情况O(n²)
• 适用性：仅适用于顺序存储的线性表。（据说，链表使用希尔排序由于链表的结构关系结点排序的效率会拖得很慢。。。）