常见排序算法之希尔排序

文章目录

• ​​1、概述​​
• ​​2、希尔排序之交换法​​
• ​​3、希尔排序之移动法​​
• ​​4、测试案例​​

1、概述

由于简单的插入排序每次数据量变多的时候，数据需要移动且交换数据的次数也会变多，继而影响效率。希尔排序就是在这个基础上进行改良，让数据能在较短的移动次数内就完成排序，继而提高排序效率。

希尔排序是希尔在1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更加高效的版本，也称为缩小增量排序（不断地除2）。核心思想：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

缩小增量的核心要领：

希尔排序就是在之前的排序算法的基础上，进行了一个改良，它最本质的目的就是希望做出一些优化，使得我们的代码移动的次数减少。继而再配合我们的交换法（冒泡排序思想）和移动法（插入排序思想）。所以学习希尔排序就需要你对冒泡排序和插入排序已经熟练掌握，不然希尔排序对你来说就又是一个新的排序（本质我们只需要学会希尔排序的缩小增量思想就行）。

2、希尔排序之交换法

在缩小增量的基础上，配合冒泡排序的使用，该方法效率并不高

public class ShellSortTest01 {
    public static void main(String[] args) {
        int[] arr = {1, 123, 10, 3, 6, 34, 66, 23, 11, 71};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void shellSort(int[] arr) {
        int temp;

        //1.每组的大小不断的减小为原来的一半，缩小增量的关键步骤
        for (int grap = arr.length / 2; grap > 0; grap /= 2) {
            //2.根据分出来的组数，遍历对应的每一组的其中一个元素，为下面的每一组数字的遍历开一头
            for (int i = grap; i < arr.length; i++) {
                //3.遍历每一组的数字，使用类似于冒泡的方式进行交换数据
                for (int j = i - grap; j >= 0; j -= grap) {
                    if (arr[j] > arr[j + grap]) {
                        temp = arr[j + grap];
                        arr[j + grap] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
        }
    }
}

3、希尔排序之移动法

在缩小增量的基础上，配合插入排序，效率较高

public class ShellSortTest02 {
    public static void main(String[] args) {
        int[] arr = {1, 123, 10, 3, 6, 34, 66, 23, 11, 71};
        shellSort2(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void shellSort2(int[] arr) {
        int insertVale;
        int insertIndex;

        //1.每组的大小不断的减小为原来的一半
        for (int grap = arr.length / 2; grap > 0; grap /= 2) {
            //2.根据分出来的组数，遍历对应的每一组的其中一个元素，为下面的每一组数字的遍历开一头
            for (int i = grap; i < arr.length; i++) {
                //3.遍历每一组的数字，使用插入排序的方式进行排序
                //其实内部就是一个插入排序，只是外面套了个缩小增量的壳
                insertVale = arr[i];
                insertIndex = i - 1;
                while (insertIndex >= 0 && insertVale < arr[insertIndex]) {
                    arr[insertIndex + 1] = arr[insertIndex];
                    insertIndex--;
                }
                if (insertIndex + 1 != i) {
                    arr[insertIndex + 1] = insertVale;
                }
            }
        }
    }
}

4、测试案例

最终我们的测试案例，使用希尔排序配合移动法

public class ShellSortTest03 {
    public static void main(String[] args) {
        int[] arr = new int[80000];

        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
        long start = System.currentTimeMillis();
        shellSort2(arr);
        System.out.println(Arrays.toString(arr));
        long end = System.currentTimeMillis();

        System.out.println("shell排序花费的时间是：" + (end - start));

    }

    public static void shellSort2(int[] arr) {
        //插入排序需要的变量
        int insertVale;
        int insertIndex;
        for (int grap = arr.length / 2; grap > 0; grap /= 2) {
            for (int i = grap; i < arr.length; i++) {
                //原始的插入排序
                insertVale = arr[i];
                insertIndex = i - 1;
                while (insertIndex >= 0 && insertVale < arr[insertIndex]) {
                    arr[insertIndex + 1] = arr[insertIndex];
                    insertIndex--;
                }
                if (insertIndex + 1 != i) {
                    arr[insertIndex + 1] = insertVale;
                }
            }
        }
    }
}

使用该方式的速率极快，这是在冒泡、选择、插入这三种中，最快的一种