7-4 快速排序中的堆栈深度

7.1节中QUICKSORT算法包含有两个对其自身的递归调用。在调用PARTITION后，左边的子数组和右边的子数组分别被递归调用。QUICKSORT中的第二次递归调用并不是必须的；可以用迭代控制来代替它。这种技术称作尾递归，大多数的编译程序都加以了采用。考虑下面这个快速排序的版本，它模拟了尾递归：

1
2
3
4
5

QUICKSORT'(A, p, r)
1  while p<r
2      do q <- PARTITION(A, p, r)
3         QUICKSORT(A, p, q-1)
4         p <- q+1

a) 论证QUICKSORT’(A, 1, Length[A])能正确地对数组A进行排序。

首先证明QUICKSORT(A, 1, Length[A])能正确地对数组A进行排序

1
2
3
4
5

QUICKSORT(A, p, r)
1  if p<r
2      then q <- PARTITION(A, p, r)
3           QUICKSORT(A, p, q-1)
4           QUICKSORT(A, q+1, r)

循环不变式：QUICKSORT(A, p, r)调用后，A[p..r]中的元素是有序的。

初始化：r-p=1时，调用QUICK(A, p, r)。因为p<r，故进入if语句块，调用q<-PARTITION(A, p, r)后，A[p..q-1]的元素一定小于A[q]，A[q+1..r]的元素一定大于A[q]，又因为A[p..r]此时只包含两个元素，所以在调用q<-PARTITION(A, p, r)后A[p..r]有序。因为此时q只能等于p或r，所以下面的QUICKSORT(A, p, q-1)、QUICKSORT(A, q+1, r)将不做任何操作。显然，循环不变式是成立的。

保持：对任意数组A下标范围内的p、r调用QUICKSORT(A, p, r)时，假设循环不变式成立，于是QUICKSORT(A, p, q-1)使A[p..q-1]有序，QUICKSORT(A, q+1, r)使A[q+1..r]有序。并且由于调用了q<-PARTITION(A, p, r)，A[p..q-1]的元素都小于A[q]，A[q+1..r]的元素都大于A[q]，于是数组A[p..r]就有序了。

终止：最外层QUICKSORT(A, 1, Length[A])调用结束时，根据循环不变式，A[1..n]有序。

QUICKSORT’调用与QUICKSORT相同的PARTITION，然后都以(A, p, q-1)调用自身。QUICKSORT以(A, q+1, r)再次调用自身，而QUICKSORT’则是让p<-q+1后执行了while循环的另一次迭代。实际上不难看出，这一操作与QUICKSORT的第二次自身调用效果相同。于是QUICKSORT’(A, 1, Length[A])能正确对数组A进行排序。

c) 修改QUICKSORT’的代码，使其最坏情况栈深度为Θ(lgn)。保持算法的O(nlgn)期望运行时间不变。

1
2
3
4
5
6
7
8

QUICKSORT''(A, p, r)
1 while p<r
2     do q <- PARTITION(A, p, r)
3        if q-p<r-q
4            then QUICKSORT''(A, p, q-1)
5                 p <- q+1
6            else QUICKSORT''(A, q+1, r)
7                 r <- q-1