Shell Sort

优化版

将步长d设置为3，即间隔三个的为一组的时候，时间复杂度达到最优

解析

这个算法一个有三层遍历：
1. 最外层遍历，负责记录每次的步长
2. 中间那层负责记录每次有几组需要遍历
3. 最里面那层对自己那组进行简单插入排序算法，跑到它能跑到的最前位置

code

void shell_sort(){

    for(int d = n / 3 ; d ; d = d / 3)
    {
        for(int start = 0 ; start < n ; start++)
        {

            for(int i = start + d ; i < n ; i+= d)
            {
                int j = i, t = q[i];
                while(j && q[j-d] > t)
                {
                    q[j] = q[j-d];
                    j -= d;
                }
                q[j] = t;
            }
        }
    }
}