package sort;

//=================================================

// File Name       :	ShellSort

//------------------------------------------------------------------------------

// Author          :	Common

import java.util.Arrays;

//类名：Arrays_Shell

//属性：

//方法：

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 && arrays[in-h] >= temp){//刚开始in是比较0和h的大小

					arrays[in] = arrays[in-h];

					in -= h;

				}

				arrays[in] = temp;

				//display();

			}

			h = (h-1)/3;

		}

	}

}

//主类

//Function        : 	ShellSort

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();

	}

}