排序算法之希尔排序

一、简介

稳定：如果A原本在B前面，而A=B，排序之后A仍然在B的前面；
不稳定：如果A原本在B的前面，而A=B，排序之后A可能会出现在B的后面；
时间复杂度： 描述一个算法执行所耗费的时间；
空间复杂度：描述一个算法执行所需内存的大小；
n：数据规模；
k：“桶”的个数；
In-place：占用常数内存，不占用额外内存；
Out-place：占用额外内存。

希尔排序是将数据分组，将每一组进行插入排序。每一组排成有序后，最后整体就变有序了。希尔排序也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

详细过程查看如下博客链接：
排序算法 —— 希尔排序（图文超详细）

算法步驟：

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

二、代码实现

public class ShellSort {

    public static void shellSort(int[] arr) {
        //声明了整型变量len表示数组长度，以及临时变量tmp和j。
        int len = arr.length, tmp, j;
        //外层循环控制增量gap的大小，初始增量为数组长度的一半，每次循环将增量减半，直到增量为1。
        for (int gap = len / 2; gap >= 1; gap = gap / 2) {
            //内层循环从增量gap开始遍历数组，从第gap个元素开始，对每个元素进行插入排序。
            for (int i = gap; i < len; i++) {
                //将当前元素arr[i]保存到临时变量tmp中。
                tmp = arr[i];
                //初始化变量j为当前元素的前一个元素（间隔gap）的下标
                j = i - gap;
                //在内层循环中，如果j仍在数组范围内且前一个元素大于当前元素，就进行插入排序的操作。
                while (j >= 0 && arr[j] > tmp) {
                    //将前一个元素后移一个间隔位置。
                    arr[j + gap] = arr[j];
                    //继续向前比较。
                    j -= gap;
                }
                //将临时保存的当前元素插入到正确的位置。
                arr[j + gap] = tmp;
            }
        }
    }
    public static void shellSort2(int[] arr) {
        int len = arr.length, tmp, j;
        for (int gap = len / 2; gap >= 1; gap = gap / 2) {
            for (int i = gap; i < len; i++) {
                tmp = arr[i];
                j = i - gap;
                while (j >= 0 && arr[j] < tmp) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = tmp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 15, 50, 7, 65, 3, 99};
        System.out.println("---排序前:  " + Arrays.toString(arr));
        shellSort(arr);
        System.out.println("希尔排序从小到大:  " + Arrays.toString(arr));
        shellSort2(arr);
        System.out.println("希尔排序从大到小:  " + Arrays.toString(arr));
    }

}

输出：

三、应用场景

希尔排序的平均时间复杂度：O(n^1.3)
所以，希尔排序的时间复杂度会比o(n^2)好一些
是一种高效的插入排序优化算法，适用于中规模数据量的排序。 通过将数据按增量分组并进行直接插入排序，希尔排序可以在处理大规模数据时保持较高的效率。 在实际应用中，希尔排序可以被用于各种需要对数据进行快速排序的场景，如 数据库索引、文件系统排序等。

参考链接：
排序算法 —— 希尔排序（图文超详细）
八大排序算法——希尔（shell）排序（动图演示 思路分析 实例代码java 复杂度分析）