#include
#include
typedef int ElementType;

/* 希尔排序 */
void ShellSort( ElementType A[], int N )
{
	int i, j, Increment;
	int count = 0;
	ElementType 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;
		}
	}
	printf( "%d\n", count );
}

int main()
{
	int A[10] = {5,15,748,8,14,63,19,20,72,62};
	int i;
	ShellSort( A, 10 );
	for( i = 0; i < 10; i++ )
	{
		printf( "%d ", A[ i ] );
	}
}