写在前面

【说明】以下代码实现最终均为递增序列，即从小到大排序。

1.头文件及类型定义

#include<stdio.h>
#define ElemType int

2.函数声明

/*函数声明*/
void DirectInsertSort(ElemType A[], int n);        //1.直接插入排序
void HalfInsertSort(ElemType A[], int n);        //2.折半插入排序
void ShellSort(ElemType A[], int n);            //3.希尔排序

3.基本操作

3.1 直接插入排序

//1.直接插入排序
void DirectInsertSort(ElemType A[], int n) {
    int i, j;
    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 (j = i - 1; A[0] < A[j]; j--)    //从后往前顺序查找待插入位置
                A[j + 1] = A[j];    //向后挪位
            A[j + 1] = A[0];    //插入指定位置
        }
}

3.2 折半插入排序

//2.折半插入排序
void HalfInsertSort(ElemType A[], int n) {
    int i, j, low, high, mid;
    for (i = 2; i <= n; i++) {
        //依次将A[2]~A[n]插入到前面已排序序列
        A[0] = A[i];    //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 (j = i - 1; j >= high + 1; j--)    
            A[j + 1] = A[j];    //统一后移元素，空出插入位置
        A[high + 1] = A[0];        //插入指定位置
        //或者  A[low] = A[0];  因为最后是在low>high时退出循环的，故low=high+1
    }
}

3.3 希尔排序

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

4.main函数

int main() {
    //1.直接插入排序
    ElemType A[11];
    for (int i = 1; i < 11; i++)
        scanf("%d", &A[i]);
    DirectInsertSort(A, 10);
    for (int i = 1; i < 11; i++)
        printf("%d\t", A[i]);
    printf("\n");
    //2.折半插入排序
    ElemType B[11];
    for (int i = 1; i < 11; i++)
        scanf("%d", &B[i]);
    HalfInsertSort(B, 10);
    for (int i = 1; i < 11; i++)
        printf("%d\t", B[i]);
    printf("\n");
    //3.希尔排序
    ElemType C[9];
    for (int i = 1; i < 9; i++)
        scanf("%d", &C[i]);
    ShellSort(C, 8);
    for (int i = 1; i < 9; i++)
        printf("%d\t", C[i]);
    return 0;
}

5.小结

一、插入排序的概念

顾名思义，就是插入(hhh),主要分两步：
① 找插入位置(比较)：得知道往哪插，就是查找咯，用顺序查找就是直接插入排序，用折半查找就是折半插入排序，所谓查找也就是比较的过程。
② 插入(移动)：和按个子大小站队一样，找到插入位置以后，你先从队里面出来，跑到要插入的位置，别人向后移动，填补你原来的位置。

二、关于三种插入排序的关系

逐渐优化：直接插入排序——>折半插入排序——>希尔排序
[解释]
给定一个乱序序列，从第2个元素开始，依次和前面元素比较(即顺序查找)，也就是进行直接插入排序。因此，每一趟直接插入排序开始时，它前面的序列都是有序的(因为前面的已经比过了)。
既然前面的元素有序，则可以折半查找来提高查找插入位置的效率，也就是折半插入排序。
试想：如果给定序列本身就由小到大，那么则只需要从第2个元素开始比较，不需要移动，由此可见直接插入排序更适用于基本有序且数据量不大的排序表，希尔排序就是基于这两点分析进一步改进的，由部分有序到整体有序。

三、关于三种插入排序的性能分析

直接插入排序
空间复杂度：O(1)
时间复杂度：O(n2)
稳定性:稳定
适用性：适用于顺序存储和链式存储的线性表
折半插入排序
空间复杂度：O(1)
时间复杂度：O(n2)
稳定性:稳定
适用：仅适用于顺序存储的线性表
希尔排序(缩小增量排序)
空间复杂度：O(1)
时间复杂度：最坏为O(n2)
稳定性:不稳定
适用：仅适用于顺序存储的线性表
【注】：当增量d=1时，希尔排序会退化为直接插入排序

四、其他说明

对直接插入排序和折半插入排序来说，每一趟排序都会得到一个部分有序的序列，这可以作为判断是否进行了直接插入排序或折半插入的依据，而希尔排序不会。
关于算法适用于顺序存储还是链式存储，主要看在算法的执行过程中，是否涉及到了对元素的随机访问，如果涉及到了对元素的随机访问，则链表不适用。就上述三种排序算法来说，直接插入排序 采用的是顺序查找，挨个找，链表也可以；而折半插入排序 采用的是折半查找，对mid指针来说，他是随机访问的，所以链表不行；希尔排序 也是同样的，因为每次增量d都是变化的，也是随机访问，所以链表不行。
需要注意的是，大部分的排序算法都仅适用于顺序存储的线性表