希尔排序

不稳定，只能顺序表使用，先追求表中部分元素有序，再逐渐逼近全部有序
希尔排序的时间复杂度约为o(n^1.3)，最坏为o(n^2)；空间复杂度o(1);

#include <iostream>
using namespace std;
const int N=100010;
int q[N],n;

void shellsort()
{
        int i, j, d, temp;

        for (d = n / 2; d > 0; d /= 2)
        {
                for (i = d; i < n; i++)
                {
                        temp = q[i];
                        for (j = i - d; j >= 0 && q[j] > temp; j -= d)
                        {
                                q[j+d] = q[j];
                        }
                        q[j+d] = temp;
                }
        }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>q[i];
    }
    shellsort();
    for(int i=0;i<n;i++)
    {
        cout<<q[i]<<' ';
    }
    return 0;
}