经典排序之希尔排序详解

tojian 2021-08-04 原文

希尔排序

1.概述

　希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

首先我们知道直接插入排序的时间复杂度最低的时候应该是序列基本有序，效率最高，在待排序的记录个数较少时，效率较高。基于这个基础理论，希尔排序的基本思想如下：

先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

技巧：

子序列的构成不是简单地“逐段分割”
将相隔某个增量dk的记录组成一个子序列
让增量dk逐趟缩短（例如依次取5,3,1）
直到dk＝1为止。

优点：

小元素跳跃式前移
最后一趟增量为1时，序列已基本有序
平均性能优于直接插入排序

如何选择最佳d序列，目前尚未解决
最后一个增量值必须为1，无除1以外的公因子
不宜在链式存储结构上实现

二、过程

这部分参考https://www.cnblogs.com/chengxiao/p/6104371.html，主要是图画的特别好

我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

三.算法分析

四、完整代码

public class ShellSort {

    public static void sort(int[] array) {
        int inner, outer;
        int temp;

        int h = 1;
        while (h <= array.length / 3) {
            h = h * 3 + 1;
        }
        while (h > 0) {
            for (outer = h; outer < array.length; outer++) {
                temp = array[outer];
                inner = outer;

                while (inner > h - 1 && array[inner - h] >= temp) {
                    array[inner] = array[inner - h];
                    inner -= h;
                }
                array[inner] = temp;
            }
            h = (h - 1) / 3;
        }
    }

    public static void main(String[] args) {

        int [] array = {5,3,0,2,4,1,0,5,2,3,1,4};
        System.out.println("Before: " + Arrays.toString(array));
        sort(array);
        System.out.println("After:  " + Arrays.toString(array));

    }
}

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