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