#include<stdio.h>
#include<algorithm>
using namespace std;

template<class T>
void ShellPass(T*& A,int d,int& n,int& count){
	int i,j;
	count++;
	for(i=d+1;i<=n;++i)
		if(A[i]<A[i-d]){
			A[0]=A[i];
			j=i-d;
			do{
				A[j+d]=A[j];
				j-=d;
			}while(j>0 && A[0]<A[j]);
				A[j+d]=A[0];
		}
		printf("the %dth pass:\n",count);
		for(i=1;i<=n;++i)
			printf("%d ",A[i]);
		printf("\n");
}

template<class T>
void ShellSort(T*& A,int & n,int& count){
	int incr=n;
	while(incr>1){
		incr=incr/3+1;
		ShellPass(A,incr,n,count);
	}
}


int main(){
	printf("input the quantity of the numbers,if quit,press 0\n");
	int n,i;
	while(scanf("%d",&n)==1 && n!=0){
		int count=0;
		int *A=new int[n+1];
		for(i=1;i<=n;++i)
			scanf("%d",A+i);
		ShellSort(A,n,count);
		printf("The sequence sorted by merge_sort:\n");
		for(i=1;i<=n;++i)
			printf("%d ",A[i]);
		printf("\n");
		sort(A+1,A+n+1);
		printf("The sequence sorted by the lib function::sort:\n");
		for(i=1;i<=n;++i)
			printf("%d ",A[i]);
		printf("\n");
	}
	return 0;
}


/*希爾排序基本思想

  基本思想
希爾排序（Shell Sort）又稱為“縮小增量排序”。是1959年由D.L.Shell提出來的。該方法的基本思想是：先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，因此希爾排序在時間效率上比前兩種方法有較大提高。
具體做法：首先確定一組增量d0，d1，d2，d3，...,dt-1()其中n>d0>d1>...>dt-1=1),對于 i=0,1,2,...,t-1,依次進行下面的各趟處理:根據當前增量di將n個元素分成di個組,每組中元素的下標相隔為di;再對各組中元素進行直接插入排序.
2、下面給出希爾排序算法的執行過程。

（1）采用希爾排序法排序的各趟的結果如下:
初始:503,17,512,908,170,897,275,653,426,154,509,612,677,765,703,94
第1趟{d1=8}:426,17,509,612,170,765,275,94,503,154,512,908,677,897,703,653
第2趟(d2=4):170,17,275,94,426,154,509,612,503,765,512,653,677,897,703,908
第3趟(d3=2):170,17,275,94,426,154,503,612,509,653,512,765,677,897,703,908
第4趟(d1=1):17,94,154,170,275,426,503,509,512,612,653,677,703,765,897,908
（2）例如，n=8，數組a的八個元素分別為：17，3，30，25，14，17，20，9。

給定實例的shell排序的排序過程

    　假設待排序文件有10個記錄，其關鍵字分別是：
        49，38，65，97，76，13，27，49，55，04。
    　增量序列的取值依次為：
        5，3，1
    　排序過程如【動畫模擬演示】。

Shell排序的算法實現

1． 不設監視哨的算法描述
  void ShellPass(SeqList R，int d)
   {//希爾排序中的一趟排序，d為當前增量
     for(i=d+1;i<=n；i++) //將R[d+1．．n]分別插入各組當前的有序區
       if(R[i].key<R[i-d].key){
         R[0]=R[i];j=i-d； //R[0]只是暫存單元，不是哨兵
         do {//查找R[i]的插入位置
            R[j+d]；=R[j]； //后移記錄
            j=j-d； //查找前一記錄
         }while(j>0&&R[0].key<R[j].key)；
         R[j+d]=R[0]； //插入R[i]到正確的位置上
       } //endif
   } //ShellPass

  void  ShellSort(SeqList R)
   {
    int increment=n； //增量初值，不妨設n>0
    do {
          increment=increment/3+1； //求下一增量
          ShellPass(R，increment)； //一趟增量為increment的Shell插入排序
       }while(increment>1)
    } //ShellSort
  注意：
　    當增量d=1時，ShellPass和InsertSort基本一致，只是由于沒有哨兵而在內循環中增加了一個循環判定條件"j>0"，以防下標越界。

2．設監視哨的shell排序算法
    　具體算法【參考書目[12] 】

算法分析

1．增量序列的選擇
    　Shell排序的執行時間依賴于增量序列。
    　好的增量序列的共同特征：
　　① 最后一個增量必須為1；
　　② 應該盡量避免序列中的值(尤其是相鄰的值)互為倍數的情況。
    　有人通過大量的實驗，給出了目前較好的結果：當n較大時，比較和移動的次數約在nl.25到1.6n1.25之間。

2．Shell排序的時間性能優于直接插入排序
    　希爾排序的時間性能優于直接插入排序的原因：
　　①當文件初態基本有序時直接插入排序所需的比較和移動次數均較少。
　　②當n值較小時，n和n2的差別也較小，即直接插入排序的最好時間復雜度O(n)和最壞時間復雜度0(n2)差別不大。
　　③在希爾排序開始時增量較大，分組較多，每組的記錄數目少，故各組內直接插入較快，后來增量di逐漸縮小，分組數逐漸減少，而各組的記錄數目逐漸增多，但由于已經按di-1作為距離排過序，使文件較接近于有序狀態，所以新的一趟排序過程也較快。
    　因此，希爾排序在效率上較直接插人排序有較大的改進。

3．穩定性
    　希爾排序是不穩定的。參見上述實例，該例中兩個相同關鍵字49在排序前后的相對次序發生了變化。
    */