【算法讲解】Scartch经典算法4之–希尔排序算法

友情提示：380元/半年，儿童学编程，就上码丁实验室。

1959年Shell发明，第一个突破O(n²)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

算法描述

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

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

按增量序列个数k，对序列进行k 趟排序；

每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

算法的Scratch实现

【算法讲解】Scartch经典算法4之--希尔排序算法

算法的C语言实现

function shellSort(arr) {

    var len = arr.length,

        temp,

        gap = 1;

    while (gap < len / 3) {         // 动态定义间隔序列

        gap = gap * 3 + 1;

}

    for (gap; gap > 0; gap = Math.floor(gap / 3)) {

        for (var i = gap; i < len; i++) {

            temp = arr[i];

            for (var j = i-gap; j > 0 && arr[j]> temp; j-=gap) {

                arr[j + gap] = arr[j];

}

            arr[j + gap] = temp;

}

}

    return arr;

}

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。