论证过程：希尔排序的正确性

希尔排序的正确性

• 一、问题引入
• 二、希尔排序是什么？
• 三、论证过程

---

一、问题引入

什么是希尔排序？提到希尔排序那么就需要先提到插入排序

图片来源于 励志学号数据结构 如上图所示，插入排序就是通过依次遍历元素并将其插入到指定位置的一种排序方法，这种排序方式在面对数据大体有序的情况时表现十分良好，而在面对杂乱无序甚至逆序的数据时效率极低，因此为了解决这种弊端就出现了插入排序的plus版——希尔排序。

---

二、希尔排序是什么？

像问题引入中提到的插入排序一样，希尔排序也是在进行多轮插入排序，只是我们进行插入排序的间隔不同

如 5，6，9，3，7，1，0这样一个序列，我们先进行间隔为5的插入排序，保证元素5有序（即任选间隔为5的两个元素，二者都为有序状态），这样我们相当于是对 5，7 ；6，1 ；9，0这三组数进行插入排序，得到序列 5，1，0，3，7，6，9，然后我们进行间隔为3的插入排序，保证元素3有序（定义类比于5有序），这样相当于是对 5，0，7，9 和 1，3，6 和 0，7，9 和 3，6 和 7，9这五组数进行插入排序得到序列为0，1，5，3，7，6，9，最后再进行间隔为1的插入排序，达到最终的有序状态

上述这个例子就是一个使用5，3，1这样的一个奇数序列进行希尔排序的大体流程，更为具体的可以自行查阅其他资料，这里正是因为先行进行了类如5排序，3排序这样的过程使得数组变得大体有序，故最后进行直接插入排序时效率很高，整体逻辑十分顺畅，只不过有一点我们很容易忽略，我们进行了5，3，1这样的插入排序后为什么之前的有序状态不会被破坏，即为什么3-排序之后数组依然保持5-有序
这也是我们今天所证明的定理：一个k-有序的数组进行h-排序后依然k-有序（h < k）

三、论证过程

这里我们摘录编程领域鼻祖高德纳先生（Donald E. Knuth）在《计算机程序设计的艺术》（The Art of Computer Programming）中关于这个问题的一段经典论证

Theorem K. If a k-ordered file is h-sorted, it remains k-ordered.

Thus a file that is first 7-sorted, then 5-sorted, becomes both 7-ordered and 5-ordered. And if we 3-sort it, the result is ordered by 7s, 5s, and 3s. Examples of this remarkable property can be seen in Table 4 on page 85.

Proof. Exercise 20 shows that Theorem K is a consequence of the following fact:

Lemma L. Let m, n, r be nonnegative integers, and let (x1 , … , xm+r) and (y1 , … , yn+r) be any >sequences of numbers such that

y1 ≤ xm+1 ,　y2 ≤ xm+2 ,　… ,　yr ≤ xm+r　(7)

If the x’s and y’s are sorted independently, so that x1 ≤ … ≤ xm+r and y1 ≤ … ≤ yn+r , the relations (7) will still be valid.

Proof. All but m of the x’s are known to be dominate (that is, to be greater than or equal to) some y, where distinct x’s dominate distinct y’s. Let 1 ≤ j ≤ r. Since xm+j after sorting dominates m + j of the x’s, it dominates at least j of the y’s; therefore it dominates the smallest j of the y’s; hence xm+j ≥ yj after sorting.

Exercise 20. Show that Theorem K follows from Lemma L.

Solution. (This is much harder to write down than to understand.) Assume that a k-ordered file R1 , … , RN has been h-sorted, and let 1 ≤ i ≤ N - k; we want to show that Ki ≤ Ki+k . Find u, v such that i ≡ u and i + k ≡ v (modulo h), 1 ≤ u, v ≤ h; and apply Lemma L with xj = Kv+(j-1)h , yj = Ku+(j-1)h . Then the first r elements Ku , Ku+h , … , Ku+(r-1)h of the y’s are respectively ≤ the last r elememts Ku+k , Ku+k+h , … , Ku+k+(r-1)h of the x’s, where r is the greatest integer such that u + k + (r - 1)h ≤ N.

接下来我们参照上述论述给出我们的更为详细的解释。

首先，要想证明这个定理我们需要先证明一个引理：

设m, n, r为非负整数，(x1 , … , xm+r)与(y1 , … , yn+r)为满足以下性质的序列：

y1 ≤ xm+1 ,　y2 ≤ xm+2 ,　... ,　yr ≤ xm+r那么如果x和y被分别排序，使x1 ≤ ... ≤ xm+r且y1 ≤ ... ≤ yn+r ，则以上关系仍成立。

这个引理通俗一点讲说的就是对于两个随机序列，如果他们满足：一个序列的前r个元素一个对应一个得小于等于另一个序列的后r个元素，那么当我们分别对这两个数组排序后，他们依然能够保持上述那样一个小一个的特点。

论证如下：
根据条件分析得出：
除开前面的那m个x，剩余的r个x都分别对应着一个比它小的y，由这个结论，我们就知道X序列中只有m个没有和它对应的那个小于等于它的y，因此对于这m+j个x，即使再不济把那m个没有对应的y的x全包含进去了，也会有j个x是有对应的，即至少有j个x能找到一个比它小的y，同时当我们对x序列进行排序之后，此时序列中的第m+j个元素Xm+j会大于等于包含自己在内的前m+j个元素，结合前面两点很自然得出对于Xm+j我们至少能在y序列中找到j个比它小的y，那么对于排序好的y序列，其中从y1到yj都是小于等于Xm+j的，故Xm+j ≥ yj，那取j为1~r的每一个数，这些不等式就是引理中提到的条件，至此，引理得证。

接下来我们开始证明原命题：
首先我们翻译得到高德纳老爷子的证明如下：
假设k有序的序列R1 , … , RN被h排序，设1 ≤ i ≤ N - k，即证Ki ≤ Ki+k。存在u、v使i ≡ u，i + k ≡ v (mod h)，其中1 ≤ u，v ≤ h。将xj = Kv+(j-1)h ，yj = Ku+(j-1)h代入引理。则y中的前r个元素Ku , Ku+h , … , Ku+(r-1)h分别小于等于x中的后r个元素Ku+k , Ku+k+h , … , Ku+k+(r-1)h ，其中r是满足u + k + (r - 1)h ≤ N的最大整数。证毕。

我相信大家读完其实有点懵，因此，以下给出我对这个证明过程的理解来加以辅助。首先这个证明方法的关键在于取下标组成满足引理要求又能恰好证明命题的两个序列，因此原论证中会取u，v满足那两个恒等式，这个过程其实形象点来说就是这样一个取数逻辑：

我们任取一个间隔为h的R的子序列，如Ri，Ri+h，Ri+2h … 然后在保证能取到的情况下取这些元素往后数k个的那个元素组成另一个序列，Ri+k，Ri+k+h，Ri+k+2h …，u为i，v为i+h的要求正是在取这两个序列的开始的元素Ri和Ri+k，之后+（j-1）h就是在向后依次按下标+h的方式取数组成两个序列

然后，当我们取数完毕之后就是使用引理的证明推到过程，这个过程也可以形象化为以下的逻辑：

由于R序列k有序，Ri ≤ Ri+k …,我们发现这两个序列自然满足引理中要求的前者元素分别小于后者元素的条件，只不过这里我们的m为0，而当我们对R序列进行h排序时，相当于是对所有的这些间隔为h的序列进行排序，反应到上面的两个序列就是让他们分别排序，由于引理，我们知道他们分别排序后依然有着这样的规律，而这个规律不正是k有序的条件吗？由于对于每一个h序列我们都能找到这个+k序列，所以当h序列取全时，因为h < k，在能取到Ri+k的情况下的Ri也能被取全，一旦取全，那么随之成立的就是序列k有序，得证