插入排序之希爾排序（Shell Sort）

希爾排序：縮小增量排序，屬於插入排序的一種，從前面的直接插入時間分析可知，其時間復雜度為O（n^2），若待排序的記錄基本有序，其時間復雜度可以提高至O（n）

基本思想：先將整個待排序的記錄序列分割為若干個子序列分別進行直接插入排序，待整個序列基本有序時，再對全體記錄進行一次直接插入排序

特點：1）子序列不是簡單的分段，而是相隔某個增量的記錄組成一個子序列

2）增量務必是素數或者說質數，而且最後一個增量一定是1，才能完成一趟完整的排序

看如下的shell排序算法：

int ShellInsert(MergeType* L, int dk) //希爾排序
{
	int nCompKey;
	int j = -1;
	for (int i = dk; i < L->len; i++ )
	{
		if (L->elem[i] < L->elem[i-dk])
		{
			nCompKey = L->elem[i];

			for (j = i-dk; j >= 0; j -= dk)
			{
				if (nCompKey >= L->elem[j])
				{
					break;
				}
				L->elem[j+dk] = L->elem[j];
			}
			L->elem[j+dk] = nCompKey;
		}
	}
	return 0;
}

這裡只是在比較的時候不是直接插入比較的時候使用的增量為1，而是dk，其他都是一樣的，如下是幾趟dk的算法：

int ShellSort(MergeType* L, int* dlta, int len)
{
	if (!L->elem)
	{
		return -1;
	}

	for (int i = 0; i != len; i++)
	{
		ShellInsert(L, dlta[i]);
	}
	return 0;
}

算法的時間復雜性：當增量序列為dlta[k] = 2^(t-k+1)-1時，希爾排序的時間復雜度為O（n^1.5），總之時間排序的復雜度優於直接插入排序

測試程序如下，其他函數定義詳見：冒泡算法的改進

#define  LISTLEN 10	
	MergeType pList; 

	pList.elem = (int*)malloc(sizeof(int)*LISTLEN);
	pList.len  = LISTLEN;
	pList.size = LISTLEN;
	ScanfList(&pList);
	
	//希爾排序
	int nDlta[] = {5, 3, 1};
	ShellSort(&pList, nDlta, ARRLEN(nDlta));

	PrintList(&pList);
	
	free(pList.elem);
	free(pT.elem);
	pList.elem = NULL;
	pT.elem = NULL;