一.思路

希尔排序是建立在插入排序的思想之上的，因为插入排序在应对数组接近有序的情况下，时间复杂度接近O(N)，故如果对数组先进行预排序，使数组接近有序，再进行直接插入排序，能大幅度降低时间复杂度

二.实现

首先完成单组实现：

int end = 0;
int x = a[end + gap];
while (end >= 0)
{if (a[end] > x){a[end + gap] = a[end];end = end - gap;}else{break;}
}

其次实现多组排序：

for (int i = 0; i < n - gap; i++)
{int end = i;int x = a[end + gap];while (end >= 0){if (a[end] > x){a[end + gap] = a[end];end = end - gap;}else{break;}}a[end + gap] = x;
}

最后实现插入排序：

while (gap > 1)
{gap = gap / 3 + 1;//gap越大，预排序次数越小，当gap=1时，进行插入排序for (int i = 0; i < n - gap; i++){int end = i;int x = a[end + gap];while (end >= 0){if (a[end] > x){a[end + gap] = a[end];end = end - gap;}else{break;}}a[end + gap] = x;}
}

三.结果输出

输入： 5, 8, 1, 6, 2, 6, 7, 3, 9, 4, 10  

输出：

四.时间复杂度

最好的情况：当该数组是有序的时候，时间复杂度为O(N)

最坏的情况：(1 + 2 + 3 +...N/gap)*gap

平均情况：N^1.3