[数据结构与算法]希尔排序算法

希尔排序简介

希尔排序也是插入排序的一种算法，是直接插入排序的的优化，也叫缩小增量排序。时间复杂度介于$O(n{\log }_2^n)$ ~ $O(n^2)$ 之间。

算法思路

??希尔排序在数组中采用 跳跃式分组 的策略。按增量进行分组，然后对分组进行直接插入排序。随后逐步缩小增量，继续按组进行直接插入排序操作，直至增量为1。

??通过增量分组排序的目的是为了让数组更接近于有序。当增量gap=1时，数组已经接近于有序，此时在使用直接插入排序的效率就会很高。从而在整体上，达到直接插入排序的优化效果。

初始数组

初始数组长度为8，所以初始增量gap = 8/2 = 4，第二个增量gap = 4/2 = 2，第三个增量gap = 2/2 = 1。 依此类推，最后一个增量一定是1，所以增量序列为 4、2、1

增量（间距）为 4：

增量（间距）为 2：

增量（间距）为 1：

希尔排序( 缩小增量排序 )代码

import java.util.Arrays;

public class ShellSort {

    public static void sort(int[] array) {
        // 定义初始增量gap 并逐级缩小增量
        for (int gap = array.length / 2; gap > 0; gap /= 2) {
            // 从增量位置开始比较插入
            for (int i = gap; i < array.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (array[j] > array[j + gap]) {
                        int temp = array[j];
                        array[j] = array[j + gap];
                        array[j + gap] = temp;
                    }
                }
            }
        }

    }

    public static void main(String[] args) {
        int[] array = new int[]{3, 2, 5, 7, 4, 8, 15, 1};
        ShellSort.sort(array);
        System.out.println(Arrays.toString(array));
    }

}

算法分析

• 最好的情况：数组是有序数组，每次增量分组都不需要进行元素移动。比较次数为 n-1 次，移动次数为 0 次，时间复杂度为 $O(n)$

• 最坏的情况：数组完全无序，每次都需要移动元素，时间复杂度为 $O(n^2)$

希尔排序的时间复杂度不好计算，普遍认为平均复杂度介于$O(n{\log }_2^n)$ ~ $O(n^2)$ 之间。

希尔排序是不稳定排序，因为分组交换过程中，可能会导致后面的元素被移到前面。

适用场景

希尔排序时直接插入排序的一种优化，可以用于大型数组中，希尔排序要比直接插入排序和简单选择排序快的多，并且数组越大，优势越大。

参考：https://www.cnblogs.com/chengxiao/p/6104371.html