void shellSort(int* a, int n)
{
int gap = n;
while (gap > 1)//循环结束时要保证gap为1
{
gap = gap / 3 + 1;//+1是为了防止n不是3的倍数时 gap最终变成0的情况
for (int i = 0; i < n - gap; i++)
{
int tmp = a[i + gap];
int j;
//将i + gap位置上的元素插入到[0, i]间隔为gap的有序区间中
for (j = i; j >= 0; j -= gap)
{
if (tmp >= a[j])
break;
a[j + gap] = a[j];
}
a[j + gap] = tmp;
}
}
}