package sortdemo;
import java.util.Arrays;
/**
 * Created by chengxiao on 2016/11/24.
 */
public class ShellSort {
    public static void main(String []args){
        int []arr ={1,4,2,7,9,8,3,6};
        sort(arr);
        System.out.println(Arrays.toString(arr));
        int []arr1 ={1,4,2,7,9,8,3,6};
        sort1(arr1);
        System.out.println(Arrays.toString(arr1));
    }
    /**
     * 希爾排序 針對有序序列在插入時采用交換法
     * @param arr
     */
    public static void sort(int []arr){
        //增量gap，并逐步縮小增量
       for(int gap=arr.length/2;gap>0;gap/=2){
           //從第gap個元素，逐個對其所在組進行直接插入排序操作
           for(int i=gap;i<arr.length;i++){
               int j = i;
               while(j-gap>=0 && arr[j]<arr[j-gap]){
                   //插入排序采用交換法
                   swap(arr,j,j-gap);
                   j-=gap;
               }
           }
       }
    }
    /**
     * 希爾排序 針對有序序列在插入時采用移動法。
     * @param arr
     */
    public static void sort1(int []arr){
        //增量gap，并逐步縮小增量
        for(int gap=arr.length/2;gap>0;gap/=2){
            //從第gap個元素，逐個對其所在組進行直接插入排序操作
            for(int i=gap;i<arr.length;i++){
                int j = i;
                int temp = arr[j];
                if(arr[j]<arr[j-gap]){
                    while(j-gap>=0 && temp<arr[j-gap]){
                        //移動法
                        arr[j] = arr[j-gap];
                        j-=gap;
                    }
                    arr[j] = temp;
                }
            }
        }
    }
    /**
     * 交換數(shù)組元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a,int b){
        arr[a] = arr[a]+arr[b];
        arr[b] = arr[a]-arr[b];
        arr[a] = arr[a]-arr[b];
    }
}