1.直接插入排序

核心思想

每一趟从数组中找出最小的元素，“插入”到数组的最前面。

核心代码

//直接插入排序
void InsertSort()
{
    int n=10,i,j;
    for (i=2;i<n;i++)
    {
        if (a[i]<a[i-1]){
            a[0]=a[i]; //哨兵
            for (j=i-1;a[j]>a[0];j--)
            {
                a[j+1]=a[j];
            }
            a[j+1]=a[0];
        }
    }
}

代码思想

第一个循环遍历过的已经排序，未遍历的就是待排序的，不断将下一个待排序的元素与已经排序的元素从后往前依次比较，将排好序的往后挪，最后将待排序元素插入应该在的位置。

举例：

28 19 5 38 22 44

第一趟：5 28 19 38 22 44

第一趟：5 19 28 38 22 44

第三趟：5 19 22 28 38 44

排序完成

2.希尔排序

核心思想

每次设置一个增量dk，一般第一趟n/2，第二趟n/4...以此类推。将每个元素以其后面dk个元素进行比较并排序。比如一共八个元素，第一次增量为4，则第一，第五个元素比较，第二，第六个元素比较...第二次增量为2，则第一，三，五，七比较，第二，四，六，八比较，最后一次增量是1，则每个元素进行比较。

核心代码

//希尔排序
void ShellSort()
{
    int dk,i,j,n=10;
    for (dk=n/2;dk>0;dk/=2)
    {
        for (i=dk+1;i<n;i++)
        {
            if (a[i-dk]>a[i])
            {
                a[0]=a[i];
                for (j=i-dk;a[j]>a[0]&&j>0;j-=dk)
                {
                    a[j+dk]=a[j];
                }
                a[j+dk]=a[0];
            }
        }
    }
}

代码思想

和直接插入排序类似。但是直接插入的增量是1，希尔排序是动态的。

举例

9 0 47 41 40 28 7 1

第一趟：9 0 7 1 40 28 47 41

第二趟：7 0 9 1 40 28 47 41

第三趟：0 1 7 9 28 40 41 47

排序完成

3.总结

稳定性

直接插入排序是稳定的，希尔排序是不稳定的。

效率

空间效率都是O（1）

时间效率：

直接插入排序：最好O（n）（基本有序的情况下） 平均O（$n^2$)

希尔排序：一般在O（n^1.3)左右