希尔排序复杂度详细分析（翻译来源：Hans Werner Lang教授）-一一网

来源：H.W. Lang Hochschule Flensburg lang@hs-flensburg.de Impressum Datenschutz © Created: 29.01.1998 Updated: 04.06.2018
希尔排序是最古老的排序算法之一，以其发明者D.L.Shell（1959年）命名[She 59]。虽然该算法速度快，易于理解，易于实现。然而，其复杂性分析却要复杂的多。 (୨୧•͈ᴗ•͈)◞︎♡粉色的字是我写的注释嗷。

@[toc]

算法思想

希尔排序的算法思想如下如下：

将数据序列存放在二维数组中
对数组的列进行排序

其结果是对数据进行了部分排序。重复上述过程，但是每次都使用较窄的数组，即列数较少。在最后一步，数组仅有一列。在每一步中，需要进行排序的序列都会增加（列数逐渐变少，每列包含的数组逐渐增多），直到最后一步完全排序为止。但是，由于在前面的步骤中获得的序列已经基本有序，因此在每个步骤中进行的排序操作是有有限。

例如：
对3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2 进行排序。
首先，将其排列成具有7列的数组（左），然后对这些列进行排序（右）：

3	7	9	0	5	1	6				3	3	2	0	5	1	5
8	4	2	0	6	1	5		→		7	4	4	0	6	1	6
7	3	4	9	8	2	  				8	7	9	9	8	2	
复制代码

依次排序之后较大的数据元素8和9已经到了所在列的末尾，但是一个较小的数字（如倒数第二列的2）也在该列末尾。下一步将该序列分为3列，并再次对其进行排序：

3	3	2				0	0	1
0	5	1				1	2	2
5	7	4				3	3	4
4	0	6		→		4	5	6
1	6	8				5	6	8
7	9	9				7	7	9
8	2					8	9	
复制代码

现在，序列已经基本有序。在最后一步将其排列成一列时，只需将6、8和9移到正确位置即可。

算法实现

实际上，数据序列不是存储在二维数组中，而是保存在一维数组中。例如，位置0、5、10、15等处的数据元素想象为具有5列的数组的第一列。通过这种方式建立索引的“列”，对每列进行插入排序。这种方法具有良好的性能。
以下程序从索引位置0到n-1对数组a进行排序，数据存放在数组cols中。因此，在第一步中将数据排列在1391376列中，在最后一步中将数据排列在一列中。（请注意，如果列数h大于待排序数据元素的总数，则基本上不执行任何操作。也就是说，一开始第一步，数据最大值是多大就给他们分配多少列是没意义的，不进行任何操作）对每列插入排序。

void shellsort (int[] a, int n)
{
    int i, j, k, h, v;
    int[] cols = {1391376, 463792, 198768, 86961, 33936, 13776, 4592,
                    1968, 861, 336, 112, 48, 21, 7, 3, 1}
    for (k=0; k<16; k++)
    {
        h=cols[k];
        for (i=h; i<n; i++)
        {
            v=a[i];
            j=i;
            while (j>=h && a[j-h]>v)
            {
                a[j]=a[j-h];
                j=j-h;
            }
            a[j]=v;
        }
    }
}
复制代码

算法分析

该算法的正确性在于最后一步（h = 1）中，对整个数组进行普通插入排序。但是由于数据是通过前面的步骤（h = 3、7、21，…）进行预排序，因此最后一步只有很少的插入排序步骤即可。上面的h序列（在下文中称为h序列）只是一种取增量的方法，实际上希尔排序的性能取决于增量到底怎么取。

背景

寄一封信需要16法郎，一张明信片需要11法郎。但是只能买到3法郎和7法郎的邮票。可以把信和明信片寄出去吗？（兄弟们寄过明信片吗？寄之前邮局已经按照距离规定好了邮费的，寄的时候需要贴上相应价钱的邮票才可以寄出，当没有相应面额的邮票的时候，你就要贴好几枚凑够价钱。比如我们邮政寄一封信1.2元，你可以贴3枚4毛钱的邮票。）
显然，问题是将数字 16 和 11 表示为线性组合 $k·3 + l·7$ ，非负整数系数k和 l。哪些自然数能由3和7的整数倍组合而成的？哪些不能？

定义：设 $g,h \in IN$ 。如果f可以表示为系数k的线性组合 $f=k \times g+l \times h$ ，我们则称f为g和h的线性组合，系数 $k,l \in IN_0$ 。
因为16是3和7的线性组合，即 $16=3 \times 3+1 \times 7$ ，所以可以准确将信封寄出去。