希爾排序

void shellsort(int *a, int N)
{
	int i, j, Increment;
	int tmp;

	for (Increment = N / 2; Increment > 0; Increment /= 2)
	{
		for (i = Increment; i < N; ++i)
		{
			tmp = a[i];
			for (j = i; j >= Increment; j -= Increment)
			{
				if (tmp < a[j - Increment])
					a[j] = a[j - Increment];
				else
					break;
			}
			a[j] = tmp;
		}
	}
}

1 希爾排序通過使用比較相距一定間隔的元素來工作，個趟比較的所用的距離隨著算法的進行而減小，直到只比較相鄰元素的最后一趟排序為止，因此，希爾排序有時也叫縮小增量排序（diminishing increment sort）。
2 希爾排序使用一個序列h1, h2, ..., ht，叫做增量序列（increment sequence），只要h1 = 1，任何增量序列都是可行的。
3 在使用增量hk的一趟排序后，對于每一個i有a[i] <= a[i + hk]，所有相隔hk的元素都被排序，此時稱文件是hk-排序的。
4 希爾排序的一個重要性質是，一個hk-排序的文件（此后將是h（k - 1）-排序的）保持它的hk-排序性，假如算法不是這樣的話，算法將失去他的意義。
5 一趟hk-排序的作用就是對hk個獨立的子數組執行一次插入排序。
6 增量序列有多種不同的選擇，他們對算法的時間復雜度影響不同

• 增量序列的一種流行選擇是使用shell建議的序列：ht為不大于 N / 2的最大整數，hk為不大于h(k + 1) / 2的最大整數，此時，算法的最壞運行時間為\(\Theta(n^2)\)
• Hibbard提出一個稍微不同的增量序列：1，3，7。。。，\(2^k\) - 1，關鍵的區別在于相鄰的增量沒有公因子，算法的最壞運行時間為\(\Theta(n^{3/2})\)
• Sedgewick提出了幾種增量序列，其最壞運行時間（也是可以達到的）為\(\mathrm{O}(n^{4/3})\)，平均運行時間猜測為\(\mathrm{O}(n^{7/6})\)，其中最好的序列{1，5，19，41，109，。。。}，序列中的項或者是9 x \(4^i\) - 9 x \(2^i\) + 1，或者是\(4^i\) - 3 x \(2^i\) + 1，通過將這些值放到一個數組中可以最容易的實現這個算法

7 希爾排序是算法非常簡單且又具有極其復雜分析的一個好例子