改进的插排--希尔排序

改进的插排–希尔排序

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminshing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

间隔大的时候，要交换的数量少

间隔小的时候，要交换的距离短

思路：给定一个间隔，按间隔跳着进行插排；然后缩小间隔再进行插排，知道最后最后间隔为1

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {8,4,7,5,6,3,2,1};
        print(arr);
        sort(arr);
    }

    static void sort(int[] a){

       //间隔的选择
        int h = 1;
        while (h <= a.length/3){
            h = h*3+1;
        }

        //每次间隔缩小
        for (int gap = h; gap > 0; gap = (gap-1)/3) {
            for (int i = gap; i < a.length; i++) {
                for (int j = i; j > gap-1; j-=gap) {
                    if(a[j] < a[j-gap]){
                        swap(a, j, j-gap);
                    }else {
                        break;
                    }
                }
            }
            System.out.println("间隔为"+gap+"排序后：");
            print(a);
        }

    }

    static void swap(int[] a, int i, int j){
        a[i] = a[i]+a[j];
        a[j] = a[i]-a[j];
        a[i] = a[i]-a[j];
    }

    static void print(int[] a){
        for (int i : a) {
            System.out.print(i + " ");
        }
        System.out.println("
");
    }
}