希尔排序一种是很常见的排序算法，该算法在1959年由Donald Shell公布。
希尔排序的奥妙
- 1、希尔排序的特殊之处是将待排序的数列看做是一个二维的矩阵，对序列的各列进行排序,我们将所有矩阵的w列的各自排序总称为w-sorting；同时我们将各列都排序完成的矩阵叫做w-ordered；
- 2、递减增量；希尔排序的过程中不断重排矩阵，使其宽度w更窄，重排后都要进行w-sorting操作；直到矩阵的宽度为1。
- 3、步长序列；在整个排序过程中使用到的宽度构成的逆序列叫做步长序列；步长序列要求首项为1，其余项递增；如：
h = {w1 = 1, w2, w3, ..., wk}
总结来说就是：假设初始矩阵的宽度为w；在得到该矩阵后对其每一列进行排序操作，排序完成后将矩阵的宽度w按照一定的序列缩小；缩小后又进行列排序；如此往返，直到宽度w=1，此时完成列排序后就得到了一个有序序列。
ps: 步长序列有很多种的选择，每一种选择都对应着一种不同样的算法，它们有不同的性能，因此与其说希尔排序是一种算法，不如说它是一种排序框架。
实例
假设有待排序序列：99,20,15,30,19,07,10,33,42,82,55,02,78,66,77
第一次取矩阵的宽度为 8，则可转化为如下：
99,20,15,30,19,07,10,33
42,82,55,02,78,66,77
经过列排序后为：
42,20,15,02,19,07,10,33
99,82,55,30,78,66,77
第二次取矩阵宽度为4，则可将已经进行列排序的上述矩阵转换成：
42,20,15,02
19,07,10,33
99,82,55,30
78,66,77
再次对矩阵列排序：
19,07,10,02
42,20,15,30
99,82,55,33
78,66,77
第三次取矩阵的宽度为3：
19,07,10
02,42,20
15,30,99
82,55,33
78,66,77
列排序后：
02,07,10
15,30,20
19,42,33
78,55,77
82,66,99
第4次取矩阵宽度为2：
02,07
10,15
30,20
19,42
33,78
55,77
82,66
99
列排序后得到：
02,07
10,15
19,20
30,42
33,66
55,77
82,78
99
最后w缩小到1：
02
07
10
15
19
20
30
42
33
66
55
77
82
78
99
再次进行列排序：
02
07
10
15
19
20
30
33
42
55
66
77
78
82
99
为何如此大费周章
既然最后将矩阵压缩到宽度为1的时候还要进行一次列排序，那么为何不直接进行排序，而要如此大费周章？
在回答这个问题之前，我们先看一个关于邮资的问题：在某国家寄一封普通的信需要50分，寄一个明信片需要35分；该国家有且仅有两种面额的邮票，4分邮票和13分邮票。请问能否恰好找到一种组合使得邮资分别与之对应呢？
相信经过一番的计算之后能够找到恰好组成50分的算法（6个4分邮票和2个13分邮票），但是并不能找到组成35分的邮资算法。
不难理解，所有能够组成的邮资都满足表达式：4m + 13n ；m,n ∈ N，这样的式子也叫做线性组合。
推而广之，使用g，h分别代表两种邮票的面额，则可组成的邮资：
f = mg + nh; m,n ∈ N(又叫做 g和h的线性组合)
尽管如此，始终还是有些邮资无法组合出来，我们将这些邮资放入一个集合：
N(g, h) = {不能有g,h线性组合成的邮资}
关注其中的最大者，将其设为x，设x(g, h) = max(N(g, h))
根据数论可以得到：x(g, h) = (g-1)*(h-1) - 1 = gh - (g + h)
不妨将上述的两种邮票面额带入其中，得到 x(4, 13) = 4 x 13 - (4 + 13) = 35；恰好35分为不能组合成的邮资的最大值。也就是说大于35分的邮资都能够恰好由这两种面额的邮票组成。
邮资问题与希尔排序的关系
我们先引入h-sorting 和 h-ordered的概念：
-
h-ordered，在一个序列中，任何距离为h的元素都保持前小后大的次序，我们就称它为h-ordered，
S[i] ≤ S[i + h] ; 0 ≤ i < n - h； - h-sorting，我们使用希尔排序的方式，将序列从逻辑上转换成有h列的二维矩阵，然后再进行列排序，这个过程就叫h-sorting。
定理K
假设矩阵经过一次 g-sorting，然后进行一次 h-sorting；那么从g-ordered到h-ordered后，该矩阵是否还有着g-ordered的特性呢？
答案是：具有g-ordered的特性。[Knuth,ACP Vol.3 p.90]
证明过程大家可以百度了解。
在回到线性组合，假设一个序列，同时满足g-ordered和h-ordered，那么不难推出它也满足(g+h)-ordered；同理合理推而广之这个序列也将是满足(mg+nh)-ordered。简而言之：能够表示为线性组合即为顺序的。
对一个同时满足g-ordered和h-ordered的序列（g和h互质）；考察其第i个元素，那么与其不能构成线性组合的最大元素步长差为：(g-1)(h-1)；在大与此步长之后的元素与i都是顺序的；也就是说能与i产生逆序的元素在i到其后(g-1)(h-1)之间；随着希尔排序的进行，这个范围也在缩小，能够产生的逆序对也就逐渐变小。由此我们不难联想到输入敏感的插入排序。
内部排序算法的实现（列排序）
列排序时，必须采用输入敏感的算法，以保证有序性可以持续改善，且总体的成本足够低廉。
对于输入敏感，我们很容易想到插入排序（insertion sort），当插入排序的输入序列有序时，它的时间复杂度就接近线性（O(n)）。因此，插入排序可以是希尔排序的内部列排序的实现。
步长序列的选择
较早且常见的一种步长序列是希尔序列：
H = {1,2,4,8,...,2^k,...}
该序列并不是一个较好的序列，采用该序列进行希尔排序，最坏的情况下将需要O(n²)的运行时间。
如：
11 4 14 3 10 0 15 1 9 6 8 7 13 2 12 5
上述序列在完成2-sorting后，必然为如下结果：
8 0 9 1 10 2 11 3 12 4 13 5 14 6 15 7
不难看出其中的逆序对为算数级数量级（1+2+3+...+7 + 8）；因此对于1-sorting仍需要：1+2...+2^(n-1)时间。
因此在使用希尔排序时，选择一个好的步长序列是至关重要的。
C/C++实现代码
void shellSort(int * nums, int count) {
int w, hs[] = {8,4,2,1}; // hs is the step sequence.
for (int i = 0; i < 4; i++) {
w = hs[i];
for (int j = 0; j < w; j++) {
// insertion sort
int row = 1, searchRow = 0, value = 0;
while (j + row * w < count) {
value = nums[j + row * w];
searchRow = row - 1;
while (searchRow >= 0 && nums[j + searchRow * w] > value) {
nums[j + (searchRow + 1) * w] = nums[j + searchRow * w];
searchRow--;
}
nums[j + (searchRow + 1) * w] = value;
row++;
}
}
}
}
网友评论