再谈希尔排序——看图理解希尔排序算法

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

希尔排序概述

希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。换句话说，一个h有序数组就是h个互相独立的有序数组编制在一起组成的一个数组（如下图）。在进行排序的时候，如果h很大，我们能够将元素移动到很远的地方，为了实现更小的h有序创造方便，用这种方式，对于任意以1结尾的h序列，我们都能够将数组排序，这就是希尔排序。

基本思想

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

即：将整个序列按照相距某个“增量”进行拆分，然后逐个对子序列进行直接插入排序，使得得到的结果基本有序，最后对基本有序的序列进行一次直接插入排序，使得整个序列有序。

希尔排序算法解析：

• 希尔排序是直接插入排序的一种改进，又称做缩小增量排序

• 希尔排序是把待排序集合计算出一个增量集合Tn

• 把待排序集合分成若干个子集，然后每个子集进行直接插入排序，知道Ti=1为止，排序结束

• 遍历次数为增量集合的count数

希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。

希尔排序与插入排序

• 当序列的个数比较少时，直接插入排序效率高；这个好理解，个数比较少，那么插入的次数也就少了

• 插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
  

• 如果序列本身就是基本有序，那么直接插入排序效率高（对几乎已经排好序的数据操作时效率高，即可以达到线性排序的效率）；

插入排序代码

JavaScript实现插入排序代码

function insertSort (arr) {
    for (let i = 1; i < arr.length; i++) {
        for (let j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
            swap(arr, j, j - 1)
        }
    }
    return arr
}

如果序列有序，那么j>=0&&arr[j]>arr[j+1]条件就是不满足的，插入操作就不会执行，效率自然就高了。

如果序列整体不是有序，但是期内 有若干有序的小段，以对序列进行分组，分割成若干个子序列，然后对每个子序列分别进行直接插入排序，当整个序列都基本有序时，注意只是基本有序时，再对全体记录进行一次直接插入排序。

希尔排序代码

JavaScript实现希尔排序代码

function shellSort (arr) {
    // 不为数组，直接返回
    if (!Array.isArray(arr)) {
        return arr
    }
    let length = arr.length
    // 数组长度少于2，不用排序，直接返回
    if (length < 2) {
        return arr
    }
    // 每次分组的间距都为 数组长度除2，即对半分。加入数组长度为8，那么gap=4。循环，直到gap为1
    for (let gap = Math.floor(length / 2); gap > 0; gap = Math.floor(gap / 2)) {
        // 对分组后的每个小组，数据进行排序,如从4开始循环到数组末尾8。
        for (let i = gap; i < arr.length; i++) {
            // j=i=4时，j-gap 即为0，j=i=5时，j-gap为1，一直循环到等分线4，如果数组左边的值大于右边的值，交互他们
            let swap = arr[i]
            for (var j = i; j >= gap && arr[j - gap] > swap; j -= gap) {
                arr[j] = arr[j - gap]
            }
            arr[j] = swap
        }
    }
    return arr
}

let testArr = [9, 3, 4, 0, 2, 8, 5, 1, 7, 6, 11, 10, 18, 15, 17, 12, 16, 13, 19, 14, -5]
console.log(shellSort(testArr))

上列分组是对半分，一般都是一种基于二分的思想，但是很多情况表明二分不是最好的方法，有的是基与gap=gap/3+1来做的，还有研究表明，使用素数效率更高。当然，原理都是一样的。

直接插入排序和希尔排序的比较：

1. 直接插入排序是稳定的；而希尔排序是不稳定的。

2. 直接插入排序更适合于原始记录基本有序的集合。

3. 希尔排序的比较次数和移动次数都要比直接插入排序少，当N越大时，效果越明显。

4. 直接插入排序适用于链式存储结构；希尔排序不适用于链式结构。

希尔排序复杂度

时间复杂度：平均O(n^1.3),最好为O(n),最坏为0(n ^ 2)

空间复杂度：O(1)

稳定性：不稳定

function shellSort2 (arr) {
    if (!Array.isArray(arr)) {
        return arr
    }
    let length = arr.length
    if (length < 2) {
        return arr
    }
    let gap = Math.floor(length / 2)
    while (gap > 0) {
        for (let i = gap; i < length; i++) {
            let temp = arr[i]
            let j = i
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap]
                j -= gap
            }
            arr[j] = temp
        }
        gap = Math.floor(gap / 2)
    }
    return arr
}

参考文章：

排序之希尔排序(shell sort) https://www.cnblogs.com/youzhibing/p/4889037.html （推荐阅读）

希尔排序 https://blog.csdn.net/woshixiazaizhe/article/details/81630762

希尔排序 shell sort https://www.jianshu.com/p/a49e9c1998d1

Javascript算法——希尔排序 https://segmentfault.com/a/1190000009461832

排序之希尔排序（JS） https://www.cnblogs.com/lidedong/p/9780259.html

转载本站文章《再谈希尔排序——看图理解希尔排序算法》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/SortingAlgorithms/8278.html