JavaScript 实现希尔排序

原理

---

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

希尔排序的基本思想是：

把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。
随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。

我们来通过演示图，更深入的理解一下这个过程。

image.png

在上面这幅图中：

• 初始时，有一个大小为 10 的无序序列。

• 在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。

• 接下来，按照直接插入排序的方法对每个组进行排序。

• 在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。

• 按照直接插入排序的方法对每个组进行排序。

• 在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。

• 按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。

• 需要注意一下的是，图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到，在排序过程中，两个元素位置交换了。

所以，希尔排序是 ** 不稳定 ** 的算法。

代码实现

---

/*************************************************************************
    @ File Name: shellSort.js
    @ Author: Rain
    @ Mail: raincruisethu@gmail.com
    @ Created Time: 一  7/30 11:14:22 2018
 ************************************************************************/
function shellSort(array) {
    let gap = Math.floor(array.length / 2);

    while (1 <= gap) {
        // 把距离为 gap 的元素编为一个组，扫描所有组
        for (let i = gap; i < array.length; i++) {
            let j = 0;
            let temp = array[i];

            // 对距离为 gap 的元素组进行排序
            for (j = i - gap; j >= 0 && temp < array[j]; j -= gap) {
                array[j + gap] = array[j];
            }
            array[j + gap] = temp;
        }
        gap = Math.floor(gap / 2); // 减小增量
    }
    return array;
}

let arr = [98, 42, 25, 54, 15, 3, 25, 72, 41, 10, 121];
console.log(shellSort(arr));