希尔排序的核心思想是，利用一个增量序列H[k]（大小为n），其中H[0]=1，对数组进行n次H[k]排序。每次H[k]排序，arr[H[k]]及其后面的元素分别有序地放置在arr[i-n*increment]中。
下面为实现的算法：
[c language=”++”]
void shellSort(vector<int>&arr)
{
//使用希尔增量序列,Hibbard增量序列为2^n-1
for (int increment = arr.size() / 2; increment >= 1; increment /= 2)
{
for (int i = increment; i < arr.size(); ++i)
{//把increment及后面的数,排序到 j-2I,j-I,j中。。。
int x = arr[i];
int j = i;
for (j = i; j >= increment; j -= increment)
{
if (x < arr[j – increment])//小于,则x应该前移
arr[j] = arr[j – increment];//把前面的数复制给j
else
break;//已经找到合适的位置
}
//把x放到合适的位置
arr[j] = x;
}
}
}
[/c]