希尔排序

希尔排序算法原理

希尔排序又称缩小增量排序。

• 基本思想：先将原表按增量ht分组，每个子文件按照直接插入法排序。同样，用下一个增量ht/2

将文件再分为子文件，再直接插入法排序。直到ht=1时整个文件拍好序。

• 关键：选择合适的增量
• 希尔排序算法：可以通过三重循环来实现

希尔排序图示

希尔排序特点

主要特点：

​ 每一趟以不同的增量进行插入排序。当d较大时，被移动的记录是跳跃式进行的。到最后一趟排序时（d=1），

许多记录已经有序，不需要多少移动，所以提高了排序的速度。

希尔排序的时间复杂度分析与选择的增量有关系。它是不稳定的排序方法。

增量的合理选择

最普通的选择就是使用数组长度的一半

这种增量从效率来说，不是非常好

增量的选择

knuth序列

h = 1

h = 3*h+1

代码

import java.util.Arrays;

public class ShellSortDemo {
    public static void main(String[] args) {
        //希尔排序,是对插入排序的优化
        int[] arr = {9, 4, 5, 6, 1, 0, 3, 2, 10, 20, 11, 24, 32, 13};
        //insertSort3(arr);
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void shellSort(int[] arr) {
        //定义序列的间隔为4

       /* int h=4;
        for (int i =h; i < arr.length; i++) {
            for (int j = i; j >h-1;j-=h) {
                if (arr[j] < arr[j - h]) {
                    swapValue(arr, j, j - h);
                }
            }
        }

         h = 2; //缩小间隔为2
        for (int i = h; i < arr.length; i++) {
            for (int j = i; j > h - 1; j -= h) {
                if (arr[j] < arr[j - h]) {
                    swapValue(arr, j, j - h);
                }
            }
        }
        h = 1; //缩小间隔为3
        for (int i = h; i < arr.length; i++) {
            for (int j = i; j > h - 1; j -= h) {
                if (arr[j] < arr[j - h]) {
                    swapValue(arr, j, j - h);
                }
            }
        }

        */

        //把上面的代码改进一下
      /*  for (int h = 4; h > 0; h /= 2) {
            for (int i = h; i < arr.length; i++) {
                for (int j = i; j > h - 1; j -= h) {
                    if (arr[j] < arr[j - h]) {
                        swapValue(arr, j, j - h);
                    }
                }
            }
        }

        */
        //再来优化,我们这个间隔,可以取数组长度的一半

     /*   for (int h =arr.length/2; h > 0; h /= 2) {
            for (int i = h; i < arr.length; i++) {
                for (int j = i; j > h - 1; j -= h) {
                    if (arr[j] < arr[j - h]) {
                        swapValue(arr, j, j - h);
                    }
                }
            }
        }
*/
        //间隔取成数组长度的一半,也不是很好,我们可以使用
        //h=1
        // h = 3 * h + 1   例如: 1,4,13,40,121,364
        //算出第一次的最最大间隔
        int jiange = 1;
        while (jiange <= arr.length / 3) {
            jiange = 3 * jiange + 1;
        }
        for (int h = jiange; h > 0; h = (h - 1) / 3) {
            for (int i = h; i < arr.length; i++) {
                for (int j = i; j > h - 1; j -= h) {
                    if (arr[j] < arr[j - h]) {
                        swapValue(arr, j, j - h);
                    }
                }
            }
        }


    }

    private static void insertSort3(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    swapValue(arr, j, j - 1);
                }
            }
        }
    }

    private static void insertSort2(int[] arr) {
        //直接插入排序,可以看作是间隔为1的希尔排序
        int h = 1;
        for (int i = h; i < arr.length; i++) {
            for (int j = i; j > h - 1; j -= h) {
                if (arr[j] < arr[j - h]) {
                    swapValue(arr, j, j - h);
                }
            }
        }
    }

    private static void swapValue(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    private static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            while (j > 0 && arr[j - 1] > arr[j]) {
                swapValue(arr, j, j - 1);
                j--;
            }
        }
    }
}