#include <stdio.h>
#include <iostream.h>

#define MAX 255
int R[MAX];

void ShellPass(int d, int n)
{/* 希爾排序中的一趟排序，d為當(dāng)前增量 */
     int i,j;
     for(i=d+1;i<=n;i++) /* 將R[d+1．．n]分別插入各組當(dāng)前的有序區(qū) */
       if(R[i]<R[i-d])
       {
         R[0]=R[i];j=i-d;  
         do {/* 查找R[i]的插入位置 */
            R[j+d]=R[j];/* 后移記錄 */
            j=j-d; /* 查找前一記錄 */
         }while(j>0&&R[0]<R[j]);
         R[j+d]=R[0]; /* 插入R[i]到正確的位置上 */
       }  
}  

void  Shell_Sort(int n)
{
    int increment=n; /* 增量初值，不妨設(shè)n>0 */
    do {
			increment=increment/3+1; /* 求下一增量 */
			ShellPass(increment,n); /* 一趟增量為increment的Shell插入排序 */
       }while(increment>1);
}  


void main()
{	int i,n;
	cout << "Please input total element number of the sequence:" ;
	cin >> n;
	if(n<=0||n>MAX)
	{
		cout << "n must more than 0 and less than" << MAX << endl;
	}
	cout << "Please input the elements one by one:" << endl;
	for(i=1;i<=n;i++)
		cin >> R[i];
	cout << "The sequence you input is:" ;
	for(i=1;i<=n;i++)
		cout << "   " << R[i];

	Shell_Sort(n);//希爾排序

	cout << endl << endl;
	cout << "The sequence after insert_sort is:" ;
	for(i=1;i<=n;i++)
		cout << "   " << R[i];
	cout << endl << endl;
	return; 
	
}