希尔排序的正确性 (Correctness of ShellSort)
希尔排序的正确性 (Correctness of ShellSort)
学希尔排序的时候，觉得有序性保持的性质十分神奇，但哪里都找不到数学证明。最后在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.
定理 如果一个序列是k有序的，在h排序后它保持k有序。
证明 引理：设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 ，则以上关系仍成立。
除m个以外所有x都大于等于某个y，其中不同的x大于等于不同的y。设1 ≤ j ≤ r。由于排序后xm+j大于等于x中的m + j个，它至少大于y中的j个。因此它大于等于y中最小的j个，故排序后xm+j ≥ yj，引理得证。
假设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的最大整数。证毕。
因此一开始7有序的序列在5排序后同时成为7有序与5有序的。如果再3排序，结果是7、5与3有序的。