package com.tju.sort;

/**
 * Created by xiangyang.laixiang on 2016/8/2.
 */
public class ShellSort {

    /**
     * 希爾排序的思路就是將數組按照一定間隔分割成多個數組
     * 繼而使用插入排序對各個數組內部進行排序
     * 最后不斷地縮小間隔直到間隔為1時排序完成
     */
    public static void shellSort(int a[],int n,int gap)
    {
        while(1<=gap)
        {
            for(int i=0;i<gap;i++)
            {
                for(int j=i+gap;j<n;j+=gap)
                {
                    int temp = a[j];
                    while(j>0&&a[j]<a[j-gap])
                    {
                        a[j] = a[j-gap];
                        j-=gap;
                    }
                    a[j] =temp;
                }
            }
            gap=gap/2;
        }
    }

    /**
     * 兩個有序數組的合并，其步驟就是遍歷兩個數組，將較小值填入
     * 新數組，最后如果數組還有剩余則全部填入結果后面即可
     * @param a
     * @param b
     * @return
     */
    public static int[] combineSortedArray(int a[],int b[])
    {
       int totalSize = a.length+b.length;
        int result[]=new int[totalSize];
        int i=0,j=0,k=0;
        while(j<a.length&&k<b.length)
        {
            if(a[j]<b[k])
            {
                result[i++]=a[j++];
            }else{
                result[i++]=b[k++];
            }
        }
        while (j<a.length)
        {
            result[i++]=a[j++];
        }
        while (k<b.length)
        {
            result[i++]=b[k++];
        }
        return result;
    }


    public static void main(String[] args)
    {
        int a[]={6,1,2,7,8,9,3,6};
        shellSort(a,a.length,3);
        for (int value : a)
        {
            System.out.println(value);
        }
    }
}