八大排序之希尔排序

希尔排序

希尔排序是一种基于插入排序的排序算法。
对于大规模乱序数组插入排序很慢，因为他们只会交换相邻的元素，因此元素只能一点一点的从数组一段移动到另一端。如果主键最小的元素正好再数组的尽头，要将她挪到正确的位置就需要N-1次移动，希尔排序为了加快速度简单的改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
希尔排序的思想就是使数组中任意相隔为h的元素都是有序的，这样的数组称为有序数组。
实现希尔排序的一种方法就是对于每个h，用插入排序将h个子数组独立的排序。但因为子数组是相互独立的，一个简单的方法就是再h- 子数组中将每个元素交换到比它大的元素之前去（将比他大的元素向右移一格）。只需要再插入排序中将移动元素的距离由1改为h即可。
PS：这个h一般为2或3

public class 希尔排序 {
    public static void main(String[] args) {
        int[] a={3,5,8,2,6,7,0,9,4,1};
        System.out.println("排序前的数组a:");
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println("排序后的数组a:");
        System.out.println(Arrays.toString(a));
    }

    private static void sort(int[] a) {
        int length=a.length;
        int h=1;
        while(h<length/3){
            h=h*3+1;//相隔3个元素进行一轮比较
        }
        while(h>=1){
            //将数组变成h有序
            for (int i=h;i<length;i++){
                for (int j=i;j>=h;j-=h){
                    if (a[j]<a[j-h]){
                        int temp=a[j];
                        a[j]=a[j-h];
                        a[j-h]=temp;
                    }
                }
            }
            h=h/3;
        }
    }
}