package sort;

import java.util.Arrays;

class Arrays_Shell{
	private int[] arrays;
	private int curNum;

	public Arrays_Shell(int max) {			//建立一个max长度的空数组
		super();
		arrays = new int[max];
		curNum = 0;
	}
	
	public void insert(int value){					//往空的数组里面增加元素
		arrays[curNum] = value;
		curNum++;
	}
	
	public void display(){									//显示数组
		System.out.println(Arrays.toString(arrays));
	}
	
	public void ShellSort(){
		int out,in;
		int temp;
		
		int h = 1;
		while(h <= curNum/3)	//求出最大的增量，5刚开始的增量为4
			h = h*3+1;						//1,4,13,40,121,....
		while(h>0){
			for(out=h;out<curNum;out++){//out从1开始递增，把out前的数两两排序
				temp = arrays[out];
				in = out;
				while(in>h-1 &amp;&amp; arrays[in-h] >= temp){//刚开始in是比较0和h的大小
					arrays[in] = arrays[in-h];
					in -= h;
				}
				arrays[in] = temp;
				//display();
			}
			
			h = (h-1)/3;
		}
		
	}
	
}

public class ShellSort {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		int maxSize = 100;
		Arrays_Shell arrays_demo = new Arrays_Shell(maxSize);
		arrays_demo.insert(58);
		arrays_demo.insert(57);
		arrays_demo.insert(56);
		arrays_demo.insert(60);
		arrays_demo.insert(59);
		arrays_demo.display();
		arrays_demo.ShellSort();
		arrays_demo.display();
	}

}