Notes on CLRS Chapter 1-2

看完Lecture 1的视频后，感觉听这些教授上课真的是一种享受！随后把Chapter 1, Chapter 2拿出来再复习一下，把一些需要记的东西记下来吧。有些内容正文上没有提到，而是作为练习给出的，所以有必要把一些解法分析什么的写下来。

 

第一章内容没什么吸引我的地方，随后的Chapter Notes倒是很吸引人（以前没读过这里）。这里提到了不少的大作，都是CS里的大牛啊。

 

第二章第一部分的插入排序中用到了循环不变量（Loop Invariants）来证明插入排序的正确性。

 

INSERTION-SORT(A, n) // sorts A[1..n], array index starts from 1
for j := 2 to n
    do key := A[j]
    i := j - 1
    while i > 0 and A[i] > key
        do A[i+1] := A[i]
        i := i - 1
    A[i+1] := key

索引j指向当前要插入的元素，而在每个外循环开始前，A[1..j-1]里存放的是已经排好序的j-1个元素（这j-1个元素原本也是在1..j-1这j-1个位置上的），我们把A[1..j-1]的这个属性称作循环不变量。循环不变量有三个属性：

 

Initialization: It's true prior to the first iteration of the loop.
Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.
Termination:  When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

 

熟悉数学归纳法的人应该可以看出它们之间的相似性：要证明某个属性正确，你需要证明一个base case和一个归纳步骤。这里的base case跟Initialization对应，归纳步骤跟Maintenance相对应。第三个步骤与数学归纳法不同，归纳法中，归纳步骤可以是无穷的，而这里当循环结束时，归纳步骤也停止了。

 

插入排序的正确性

 

初始化：j=2时，A[1]中只有一个元素，当然也就是已经排好序了。

维护性：外层for循环将A[j-1], A[j-2], A[j-3]等等往后移动一个位置，直到找到A[j]的合适位置为止，而后A[j]被插入到这一位置上去。可以看出，在本次循环结束后，下一次循环j := j + 1开始之前，A[1..j]是满足循环不变量的维护性的，即A[1..j]是排好序的。

终止：最后当循环终止时，j = n + 1，我们知道A[1..n]是已经排好序的，这也正是我们想要做的。即算法是正确的。

 

第二部分主题为分析算法，这在Lecture 1中讲得已经很详细了。 

 

选择排序（Selection Sort）--习题2.2-2

 

选择排序的步骤如下：

1. 找到数组中的最小元素。
2. 将它与第一个元素交换。
3. 在剩下的子数组中重复以上过程（每次开始位置都向前增加一个）直到数组中只剩下一个元素。

 整个过程重复n-1次，最后剩下一个元素当然已经是排好序的了。

 

SELECTION-SORT(A, n)
for j := 1 to n - 1   // n-1
    min := A[j]
    do for i := j to n  // n - j
        do if min < A[i]
            then min := A[i]
    swap(A[i], A[j])  // we have exactly n - 1 swaps,  (n-1)*Theta(1) = Theta(n).

 

第一次外循环结束后，A[1]中存放的是A中最小的元素，假定在第j个外循环前，A[1..j-1]存放的是A中前j-1个小的元素，且已经排好序了，那么当第j次循环结束后，A[1..j]中将存放的是A中前j个小的元素，并且也是排好序的。当第n-1次循环结束后，A[1..n-1]中存放的是A中前n-1小的元素，且已排好序，而剩下的第n个元素不需要处理，因为它就是整个数组中最大的一个。这就是选择排序的循环不变量。

 

注意到选择排序的内外循环都不依赖于数组元素，因此它的分析也是很简单，外循环有n-1次，每一次内循环都需要扫描n-j次，因此最好和最坏情况下T(n)都是一样的，即T(n)=(n-1 + n-2 + ... + 1)*Theta(1) + (n-1)*Theta(1) = n(n-1)/2*Theta(1) + Theta(n) = Theta(n^2)。因此选择排序也只对较小的n有效。

 

第三部分讲到了分治法的设计思想，这在Lecture 3中才讲到。实际上归并排序就是一种分治的思想。 

 

二分查找（Binary search）--习题2.3-5

 

线性查找(2.1-3)的最坏时间为Theta(n)。对于有序的数组，查找的时间可以约束在Theta(lg n)内。我们可以检测数组的中间元素，然后将查找元素不可能在其中出现的一半消去不用考虑。二分查找算法重复这个过程，每次都将余下的数组减半。简单的分析可以知道最坏时间为Theta(lg n)。

 

冒泡排序（Bubble Sort）--习题2-2

 

BUBBLESORT(A)
for i := 1 to length[A]
    do for j := length[A] downto i + 1
        do if A[j] < A[j-1]
            then swap(A[j], A[j-1])

  

当i=1时，内层循环会不断地将较小的元素向前移动，内层循环结束时A[1]中将存放的是整个数组中最小的元素，且是有序的。对每一步外层循环i执行前，A[1..i-1]中存放的是前i-1个最小的元素，并且是有序的，这样当第i次循环执行结束后，A[i]中将存放的是第i小的元素，因此在第i+1次循环执行前，A[1..i]中将存放的是前i个小的元素，同时也是有序的。

 

冒泡排序的循环同样也是不依赖于数组元素的。swap操作依赖元素的顺序，最坏情况在输入元素逆序的时候出现。最坏情况运行时间为Theta(n^2)。

 

这一章的Chapter Notes中提到，据Knuth所说算法一词来源于一名19世纪波斯数学家的名字al-Khowarizmi（The Art of Computer Programming）。这里还提到了D. L Shell于1959年提出的Shell排序，Shell排序在输入的周期子序列上使用插入排序，从而产生了一种更快速的排序算法。

 

这里顺便给出Shell排序的原理与简单描述，至于分析，据大百科全书上说: This algorithm is an example of an algorithm that is simple to code but difficult to analyze theoretically (http://en.wikipedia.org/wiki/Shell_sort 以下的内容也来源于此). 等我看懂了再说吧！

 

SHELLSORT(A, n)       // array index starts from 0, n = length(A)
inc := round(n/2)
while inc > 0
    do for i := inc to n - 1      // 注意看如果inc=1下面就是插入排序
        do temp := A[i]
           j := i
           while j >= inc and A[j-inc] > temp
               do A[j] := A[j-inc]
                  j := j - inc
           A[j] := temp
       inc := round(inc/2.2) 

Shell排序实际上是插入排序的一种推广，利用了插入排序在几乎已经有序的输入上有较好的性能这一特性。它改进了插入排序使其允许在输入中相距较远的元素之间进行比较与交换。Shell排序的最后一步就是普通的插入排序，但是到最后一步的时候整个序列已经可以保证是几乎有序的了。

 

Shell排序的原理是重排整个序列使其每隔h个元素构成的子序列有序。我们称这样的序列是h有序的。如果之后继续操作对该序列进行k排序，那么这个序列仍然是h有序的。比如，如果一个序列是5有序的，即所有的每隔4个元素取一个元素构成的子序列是有序的，之后再对其进行3排序，那么这个序列将即是5有序也是3有序的。

 

算法使用一个正整数序列，称为增量序列（increment sequence）。任何序列都可以，只要这个序列以1结尾就行（最后一步是普通的插入排序）。但是不同的增量序列会产生不同的性能。算法首先进行的是区间插入排序（gap insertion sort），区间的大小就是增量序列的第一个元素。所谓区间插入排序就是对每隔这个gap取得的元素构成的子序列进行的排序。比如我们有输入[13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10]，第一个增量序列的元素为5，那么算法首先会对[13 25 45 10]这几个元素使用插入排序，随后是[14 59 27]，[94 94 73]等等。可以从下面的这个图来看会更直观一些：

 

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

 

对每一列使用插入排序，得到：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

这样列表看起来是这样子[10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45]。如果第二个增量是3，插入排序会在下面的列中进行：

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

 排完序以后，

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

现在整个列表为[10 14 13 25 23 33 27 25 29 39 65 73 45 94 82 94]，既然整个列表几乎要有序了，我们可以进行增量为1的插入排序了。

 

尽管Shell排序的编码很容易，但是分析它的性能却是非常难的，并且依赖于增量序列的选择。这个算法是第一个打破二次渐近时间障碍的算法中的一个，但是这一事实直到它的发现以后的相当一段时间后才被证明。

 

Donald Shell推荐的初始增量序列是[1,2,4,8,...,2^k]，他的原始实现在最坏情况下需要O(n^2)的比较和交换操作。而通过将2^k换成2^(k-1)就可以将最坏时间提高到O(n^(3/2))。

 

希望从应用的角度来看我已经讲清楚了。