终于理解希尔排序与插入排序

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

希尔排序(Shell sort)

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

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

动图演示

希尔排序.gif

说明：

• 原始数组为【8，9，1，7，2，3，5，4，6，0】
• 初始增量为gap=length/2=5, 即整个数组被分为5组，相同颜色为一组
• 对这5组分别进行直接插入排序，可以看到小的元素被调到前面
• 再次迭代缩小增量gap=5/2=2，数组被分为2组, 相同颜色即一组
• 对以上2组再分别进行直接插入排序
• 再次递归缩小增量gap=2/2=1, 此时，整个数组为1组

代码实现

function shellSort(arr) {
    varlen = arr.length;
    for(vargap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
        // 注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行
        for(vari = gap; i < len; i++) {
            varj = i;
            varcurrent = arr[i];
            while(j - gap >= 0 && current < arr[j - gap]) {
                 arr[j] = arr[j - gap];
                 j = j - gap;
            }
            arr[j] = current;
        }
    }
    returnarr;
}

希尔排序与插入排序关系

希尔排序是在插入排序的基础上进行的一中改进的算法，希尔排序是将一个原序列分成几个子序列，对于每个子序列来所都进行一次插入排序，而依据不同的子序列划分大小，最后子序列为1时，此时插入排序跟原来的插入排序就是一模一样的了，只不过现在的队列比原来的要有序的多。

所以希尔排序就是将原序列进行了一些整理，将其变得有序一些，而我们都知道，对于插入排序这个O（N2）级别的算法来说，越是有序的序列，它所需要的时间越少，甚至在某些情况下可以逼近O（N），这就是希尔排序对于插入排序的改良。

朵拉姐【ITI2018】的前端摸鱼技术群

欢迎大家技术交流 内推 摸鱼 求助皆可 - 链接

系列链接（后续都会更新完毕）

• 一图看懂快速排序

• 插入排序（Insertion Sort）

• 冒泡排序与选择排序的区别