希尔排序 | Siyao's Blog

思想

希尔排序的实质是分组插入排序，又称缩小增量排序。

该方法的基本思想是：

先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的），对这些子序列分别进行直接插入排序
依次缩减增量再进行排序
待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

例子

现在我们要将这样一个数组排序，一共有10个元素

第一次增量 gap = 10/2 = 5

整个数组被分成了5个子数组，分别是[49,13]，[38,27]，[65,49]，[97,55]，[26,4]
然后对这五个子数组进行插入排序，得到下面结果

第二次增量 gap = 5/2 = 2

这次我们把整个数组分成了两个子数组，分别是[13,49,4,38,97],[27,55,49,65,26]
对这个两个子数组排序，结果如下：

第三次增量 gap = 2/2 = 1
此时整个数组已经接近有序，对整个数组进行全排列

最终得到数组有序

代码

//希尔排序
void HillSort(int a[], int len) {
    int delta = len/2;
    while (delta > 0) {
        for (int i = 0; i < delta; i++) {//分成了delta个子序列
            //对每个子序列进行插入排序
            for (int j = i + delta; j < len; j = j + delta) {
                int jj = j - delta;
                int temp = a[j];
                while ((a[jj] > temp)&&(jj>=0)) {
                    a[jj + delta] = a[jj];
                    jj -= delta;
                }
                //插入
                a[jj + delta] = temp;
            }
        }
        delta = delta / 2;
    }
}

优化

白话经典算法系列原文是这么说的

很明显，上面的shellsort1代码虽然对直观的理解希尔排序有帮助，但代码量太大了，不够简洁清晰。因此进行下改进和优化，以第二次排序为例，原来是每次从1A到1E，从2A到2E，可以改成从1B开始，先和1A比较，然后取2B与2A比较，再取1C与前面自己组内的数据比较…….。这种每次从数组第gap个元素开始，每个元素与自己组内的数据进行直接插入排序显然也是正确的。

我理解了一下，思路就是把在序列中提取子序列的过程简化了，我们可以从第gap个元素开始，向后遍历到序列末尾，可以个元素都跟其所在的子序列中位于它前面的数字做插入排序，最终就会得到一个有序数列了~

画个图表示一下吧，还是刚才那个序列，比如说此时进行到第二次排序了，gap=2的情况：

从a[2]开始遍历，此时a[2]所在的子序列为[a[0],a[2],a[4],a[6],a[8]]，需要将a[2]和位于它前面的a[0]比较，插入到合适的位置：

指针后移一位，同上此时a[3]所在的子序列为[a[1],a[3],a[5],a[7],a[9]]，需要将a[3]和位于它前面的a[1]比较，插入合适的位置：

接下来指针指向a[4],此时需要将a[4]和位于它前面的a[2]、a[0]比较，插入合适的位置：

下面重复上面的步骤：

此处省略剩余步骤…..最终可以将数组排列至有序状态

现在可以上代码了~

//希尔排序
void HillSort(int a[], int len) {
    int delta = len/2;
    while (delta > 0) {
        for (int i = delta; i < len; i++) {//遍历
            //对该元素子前面的子数组进行插入排序
            int temp = a[i];
            int jj = i - delta;
            while ((jj >=0)&&(a[jj]>temp)){
                swap(a[jj], a[jj+delta]);
                jj -= delta;
            }
        }
        delta = delta / 2;
    }
}

参考

MoreWindows Blog 白话经典算法系列