前言：

插入排序（稳定排序）的基本思想是：
将数组的第一个数认为是有序数组，从后往前（从前往后）扫描该有序数组，把数组中其余n-1个数，根据数值的大小，插入到有序数组中，直至数组中的所有数有序排列为止。这样的话，n个元素需要进行n-1趟排序。时间复杂度为O(n*n）;但是在同样的数据下，要比冒泡法以及选择排序法好得多。
有位博主写得很Q的解析，请点击

# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;
int a[1000];
vector<int> q;
int n;


void Charu_sort(int left,int right){       //从下标2开始，双重for循环
     for(int i=left+1;i<=right;++i){
         if(a[i]<=a[i-1]){
             a[0] = a[i];
             int j=i-1;
    		   for(;a[j]>a[0];--j)  a[j+1] = a[j];
            a[j+1] = a[0];
         }
    }
     return ;
    
}
int main(void)
{
    cin>>n;
    srand(unsigned(time(NULL)));
    for(int i=1;i<=n;++i){
        a[i] = rand()%10+1;
        q.push_back(a[i]);
    }
    sort(q.begin(),q.end());       //主要是看看自己写的排序是否正确
    for(int i=0;i<n;++i) cout<<q[i]<<' ';
    cout<<endl;
    Charu_sort(1,n);
    for(int i=1;i<=n;++i){
        cout<<a[i]<<' ';
    }
    return 0;
}

希尔排序

首先我们得知道希尔排序就是直接插入排序法改进而来，那我们就得想想为什么要改进？直接插入排序法的弊端在哪里？

（摘自大话数据结构）
从这段话我们可以看出，当直接插入排序满足上述两个条件时，效果是很好的，问题就在于这两个条件不一定都存在，这时我们就可以去创造条件，这也是希尔想到的改进优化方法。（记录数意思就是每一个子序列要排序的数字要比较少）

希尔排序思想：

设待排序元素序列有n个元素，首先取一个整数increment（小于n）作为间隔将全部元素分为increment个子序列，所有距离为increment的元素放在同一个子序列中，在每一个子序列中分别实行直接插入排序。然后缩小间隔increment，重复上述子序列划分和排序工作。直到最后取increment=1，将所有元素放在同一个子序列中排序为止。

由于开始时，increment的取值较大，每个子序列中的元素较少，排序速度较快，到排序后期increment取值逐渐变小，子序列中元素个数逐渐增多，但由于前面工作的基础，大多数元素已经基本有序，所以排序速度仍然很快。

总结起来就几个字，设置一个增量序列跳跃分割来达到基本有序，最后插入排序
(其实现的代码跟直接插入代码区别不大)

# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;
int a[1000];
vector<int> q;
int n;


void Charu_sort(int left,int right){
    int i,j;
    int len = n;    //len 为增量序列，do while 进行循环，知道len==1为止
    do{            //下面的代码跟直接插入代码没什么区别，可以理解为这里的步数为一个变量
        len = len/3+1;       //而直接插入的步数为1步
        for(i=len+1;i<=right;++i){
            if(a[i]<a[i-len]){
                a[0] = a[i];
                for(j=i-len;j>0 && a[j]>a[0];j-=len){
                    a[j+len] = a[j];
                }
                a[j+len] = a[0];
            }
        }
    }while(len>1);
    return ;
}
int main(void)
{
    cin>>n;
    srand(unsigned(time(NULL)));
    for(int i=1;i<=n;++i){
        a[i] = rand()%10+1;
        q.push_back(a[i]);
    }
    sort(q.begin(),q.end());
    for(int i=0;i<n;++i) cout<<q[i]<<' ';
    cout<<endl;
    Charu_sort(1,n);
    for(int i=1;i<=n;++i){
        cout<<a[i]<<' ';
    }
    return 0;
}

对了，关于希尔排序increment（增量）的取法：

增量increment的取法有各种方案。最初shell提出取increment=n/2向下取整，increment=increment/2向下取整，直到increment=1。但由于直到最后一步，在奇数位置的元素才会与偶数位置的元素进行比较，这样使用这个序列的效率会很低。后来Knuth提出取increment=n/3向下取整+1.还有人提出都取奇数为好，也有人提出increment互质为好。应用不同的序列会使希尔排序算法的性能有很大的差异。

希尔排序是一种不稳定算法