package com.jll.sort;
public class ShellSort {
  int[] arr;
  int size;
  
  public ShellSort() {
    super();
  }
  
  public ShellSort(int size) {
    this.size = size;
    arr = new int[size];
  }

  /**
   * @param args
   */
  public static void main(String[] args) {
    ShellSort ss = new ShellSort(10);
    for(int i=0;i<10;i++){
      ss.arr[i] = (int) ((Math.random()*100)+1);
      System.out.print(ss.arr[i]+" ");
    }
    ss.shellSort();
    System.out.println();
    System.out.println("after sort:");
    for(int i=0;i<10;i++){
      System.out.print(ss.arr[i]+" ");
    }
    
  }
  
  public void shellSort(){
    int h = 1;
    while(h<=size/3){
      h = h*3+1;
    }
    for(;h>0;h=(h-1)/3){
      for(int i=h;i<size;i++){
        int temp = arr[i];
        int j = i;
          while(j>h-1&&arr[j-h]>temp){
            arr[j]=arr[j-h];
            j-=h;
          }
          arr[j]=temp;
        }
      }
    }
  }