#include <iostream>
using namespace std;

void shellPass(int arr[],int len,int gap)
{
	int i,j,key;
	//步长不总为1的插入排序
	for ( i = gap; i < len; i++ )
        {
		j = i - gap;
		key = arr[i];             
		while (( j >= 0 ) && ( arr[j] > key ))
		{
			arr[j + gap] = arr[j];
			j = j - gap;			//在已排序序列中寻找合适位置插入key
		}
		arr[j + gap] = key;
		for(int i=0;i<len;i++)
			cout<<arr[i]<<" ";
		cout<<endl;
        }
}

void shellSort(int arr[],int len)
{
	int gap=0;
	while(gap<=len)
		gap=gap*3+1;	//确保最终步长为1
	while(gap>0)
	{
		shellPass(arr,len,gap);
		gap=(gap-1)/3;
	}
}

int main(int argc, char* argv[])
{
	int arr[]={10,54,2,3,1,0,3,5};
	int len=8;
	shellSort(arr,len);
}