希尔排序是将元素进行分组，组的大小逐渐扩大，然后对每个分组利用直接插入排序算法使分组内有序。当组的大小刚好为 n 的时候，再调用直接插入排序就可以使得整个数组有序了。

分组

如何描述组的大小变化呢？利用一个增量 dk 描述。当组逐渐扩大的时候，dk 就会逐渐减小，例如我们可以用如下 for 循环来描述 dk 的变化：

for (int dk = n / 2; dk >= 1; dk /= 2) {
	// 直接插入排序
}

对于 dk 的唯一的要求就是最后一次的循环 dk 一定为 1.

当我们确定了 dk 后，分组就唯一确定了。例如对于一个长度为 10，dk = 3 的数组来说，分组就为：

[0,3,6,9]
[1,4,7]
[2,5,8]
==========
[3,6,9]
[4,7]
[5,8]
[6,9]

直接插入排序

在确定分组后，我们要做的就是对分组内的元素进行排序。

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

完整实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
int n;
int a[N];

void shell_sort() {
    for (int dk = n / 2; dk >= 1; dk /= 2) {
        // insert_sort
        for (int i = dk; i < n; i++) {
            int t = a[i], j = i;
            while (j >= dk && a[j - dk] > t) {
                a[j] = a[j - dk];
                j -= dk;
            }
            a[j] = t;
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    
    shell_sort();
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    return 0;
}