请问我写的希尔排序哪里有问题，运行了一下，与其他博客写的效率完全不在一个等级啊，可以怎么修改一下？

#include <iostream>
#include<ctime>
#include<cstdlib>


using namespace std;

clock_t start;
clock_t e;

int main()
{
    int n;
    cin >> n;
    int* a = new int[n];
    start = clock();
    for (int i = 0; i < n; i++)
    {
        a[i] = rand();
    }
    int s = n / 3 +1;
    do {
        for (int i = 0; i < s; i++)//分组后，进行每组排序的次数
        {
            for (int j = i+s; j < n;)//每组的第二个元素
            {
                for (int k = i; k < j;)//从首元素开始遍历，直至下标位j的元素
                {
                    if (a[k] > a[j])//寻找符合条件的位置插入
                    {
                        for (int q = j; q > k;)//进行插入排序
                        {
                            int t = a[q];
                            a[q] = a[q - s];
                            a[q - s] = t;
                            q -= s;
                        }
                    }
                    k += s;
                }
                j += s;
            }
        }
        s = s / 3 +1;
    } while (s != 1);
    e = clock();        //程序结束用时
    double endtime = (double)(e - start) / CLOCKS_PER_SEC;
    cout << "Total time:" << endtime << endl;        //s为单位
    cout << "Total time:" << endtime * 1000 << "ms" << endl;
}