shell sort 希尔排序

希尔排序的核心思想是，利用一个增量序列H[k]（大小为n），其中H[0]=1，对数组进行n次H[k]排序。每次H[k]排序，arr[H[k]]及其后面的元素分别有序地放置在arr[i-n*increment]中。

下面为实现的算法：

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;
		}
	}
}