希爾排序--C語言

希爾排序(Shell’s Sort)是插入排序的一種又稱「縮小增量排序」（Diminishing Increment Sort），是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法。
基本思路是先取一個小於n的整數d1作爲第一個增量，把檔案的全部記錄分組。所有距離爲d1的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然後，取第二個增量d2，直至增量爲1；
利用C語言寫的希爾排序的演算法如下：
平均時間複雜度爲O(N**d)，最壞時間複雜度爲O(NN)，穩定性爲不穩定；

#include <stdio.h>

void shell_Sort(int A[],int N); 

int main (void)
{
	int i;
	int arr[21] = {2,6,9,11,3,1,7,4,17,26,14,56,90,67,43,32,12,19,100,23,0}; 
	shell_Sort(arr,21);
	for (i = 0; i< 21; i++)
	{
		printf("%d ",arr[i]);
	}
	
	return 0;
} 

void shell_Sort(int A[],int N)
{
	int i,j;
	int D;//儲存希爾增量的值
	int Tmp;//儲存臨時的值
	for(D = N/2; D > 0;D /= 2)
	{
		for(i = D; i < N; i++)
		{
			Tmp = A[i];//相當於第二張摸的牌 
			for( j = i; j >= D && A[j - D] > Tmp; j -= D)//用Tmp去跟前面D間隔的元素進行排序 
			{
				A[j] = A[j - D];//空出個位置給Tmp 
			}
			A[j] = Tmp;//此時j就是Tmp位置 
		}
	} 
}