Heading

从插入排序的分析可知，直接插入排序算法的时间复杂度为O（n^2）,但若待排序列为“正序”时，其时间复杂度可以提高到O（n），由此可见它更适用于基本有序的排序表和数据量不大的排序表。希尔排序正式基于这两点分析对直接插入排序改进而得来，又称为缩小增量排序。

希尔排序的基本思想是：先将待排序表分割成若干形如L[i,i+d,i+2d,...,i+kd]的特殊子表，即把相隔某个增量的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。

到目前为止，尚未求得一个最好的增量序列，具有较好的局部有序性。

希尔增量序列的一般方法是：d(1) = n/2，d(i+1)=floor(d(i)/2)，并且最后一个增量等于1。

点击查看代码

/**
 * 希尔排序
 * @param {*} arr 
 * @param {*} n 
 */
export function ShellSort(arr = [], n = 0) {
    let gap = ~~(n / 2), j, tmp;
    while (gap >= 1) {//gap为增量序列的步长
        for (let i = gap; i < n; i++) {//i执行排序的每一趟
            if (arr[i] < arr[i - gap]) {
                tmp = arr[i]
                j = i
                while (j >= 0 && tmp < arr[j - gap]) {//寻找当前值arr[i]的插入位置j
                    arr[j] = arr[j - gap]//将子序列的前一个值向后移动
                    j -= gap
                }
                arr[j] = tmp
            }
        }
        gap = ~~(gap / 2)
    }
    return arr;
}

性能分析如下：

• 空间效率：仅适用了常数个辅助单元，空间复杂度为O（1）
• 时间效率：由于希尔排序的时间复杂度依赖与增量序列的函数，这涉及到数学上尚未解决的难题，所以其时间复杂度分析比较困难。当n在某个特定范围时，希尔排序的时间复杂度约为O（n^1.3）。在最坏情况下时间复杂度为O（n^2）。
• 稳定性：当相同关键字的记录被划分到不同子表时，可能会改变他们之间的相对次序，因此希尔排序是一种不稳定的排序方法。
• 适用性：仅适用于线性表为顺序存储的情况。