7.1-1 参照图7-1的方法，说明PARTITION在数组A=<13,19,9,5,12,8,7,4,21,2,6,11>上的操作过程。
答:golang实现：
// Partition 分解重排步骤
func Partition(a QuickSortInterface, p int, r int) int {
x := a.Get(r)
i := p - 1
for j := p; j < r; j++ {
if a.Get(j) < x {
i++
a.Swap(i, j)
}
}
a.Swap(i+1, r)
return i + 1
}
结果为:
[9 5 8 7 4 2 6 11 21 13 19 12]
7.1-2 当数组A[p..r]中所有元素的值都相同时，PARTITION返回的q值是什么？修改PARTITION，使得当数组A[p..r]中所有元素的值都相同时，q=[(p+r)/2]
答：PARTITION返回的值为r;把第四行代码改为
if a.Get(j) < x && j%2 == p%2
7.1-3 请简要地证明：在规模为n的子数组上，PARTITION的时间复杂度为O(n)
答：在for循环中，对于子数组的每个元素，都会做一次判断，在循环外的操作时间代价都是常数级的，所以复杂度为O(n)。
7.1-4 如何修改QUICKSORT，使得它能够以非递增进行排序？
答：将a.Get(j) < x判断条件改为a.Get(j) > x即可。
7.2-1 利用代入法证明：正如7.2节开头提到的那样，递归式T(n) = T(n-1) + O(n)的解为T(n) = O(n^2)
答：猜测的解为:T(n) = O(n^2)
代入递归式T(n) = T(n-1) + O(n)得:
T(n) = c (n-1)^2 + c2n
T(n) = c(n^2 - 2n +1) + c2n
T(n) = cn^2 - (c2-2c)n +c
所以T(n) = O(n^2)
7.2-2 当数组A的所有元素具有相同值时，QUICKSORT的时间复杂度是什么？
答：时间复杂度是n^2。 因为PARTITION步骤将会永远发生在子数组的最后一个位置。
7.2-3 证明：当数组A包含的元素不同，并且是按降序排列的时候，QUICKSORT的时间复杂度为O(n^2)
答：因为是按降序排列的，所以在PARTITION步骤的时候，都会进行到子数组的最后一个位置。
7.2-4 银行一般会按照交易时间来记录某一账户的交易情况。但是，很多人却喜欢收到的银行对账单是按照支票号码的顺序来排列的。这是因为,人们通常都是按照支票号码的顺序来开出支票的，而商人也通常都是根据支票编号的顺序兑付支票。这一问题是将按交易时间排序的序列转换为按支票号排序的序列，它实质上是一个对几乎有序的输入序列进行排序的问题。请证明：在这个问题上，INSERT-SORT的性能往往要优于QUICKSORT
答：假设A[i]离它正确的位置最多偏离c个位置，那么对于插入排序来说：它的时间复发度就为O(cn)= O(n),而对于快速排序来说每次循环都要进行n-c次的PARTITON步骤，因此它的时间复杂度为O(n^2),所以插入排序性能更好。
7.2-5 假设快速排序的每一层所做的划分的比例都是1-a : a,其中0<a<=1/2，且是一个常数。
试证明：在相应的递归树中，叶结点的最小深度大约是-lgn/lga，最大深度大约是-lgn/lg(1-a)(无需考虑整数舍入问题)
答：最小深度和较小的子数组有关，子数组的数组大小正比例于a,当n*a^k = 1时，此时便为叶节点了。此时k = - lgn/lga；同理最大深度大约为 - lgn/lg(1-a)
7.2-6 试证明：在一个随机输入数组上，对于任何常数0<a<=1/2,PARTITION产生比1-a:a更平衡的划分的概率约为1-2a
答：如果在PARTITION的步骤需要分解的更加平衡，则an<=k <= (1-a)n
这个的概率是:((1-a)n-an+1)/n = 1-2a
7.3-2 在RANDOM-QUICKSORT的运行过程中，在最坏的情况下，随机数生成器RANDOM被调用了多少次？在最好的情况下呢？
答：最好的情况下，是每次都随机到数组的中间值，此时的次数为lgn,最好的情况下，每次都随机到数组的最大值，此时的次数为n
7.4-6 考虑对PARTITION过程做这样的修改：从数组A中随机选出三个元素，并用这三个元素的中位数对数组进行划分。求以a的函数形式表示的、最坏划分比例为a:(1-a)的近似概率，其中0<a<1
答: 为了简单，假设数组由1-n个数组成，如果我们用k去表示中位数，那么以最坏划分比例的近似概率就是an<k<(1-a)n的概率。此时选出三个元素不满足这样的k的概率等于这三个数中至少两个数来自[1,an]或者至少两个数来自[(1-a)n,n]。两边都由相同的数组大小，所以选出这样三个数的概率为2(a^3 + 3(1-a)a^2)，所以落在最坏的划分区间的概率是这个概率的反面情况，
即：1-2(a^3 + 3(1-a)a^2) = 1 + 4a^3 - 6a^2
思考题
7-1
答：(1).
第一次执行时，x=13,p=1,r=12,i=0,j=13
数组的排列情况:13,19,9,5,12,8,7,4,11,2,6,21
第二次执行时, x=13,p=1,r=12,i=1,j=11
数组的排列情况:6,19,9,5,12,8,7,4,11,2,13,21
第三次执行时,x=13,p=1,r=12,i=2,j=10
数组的排列情况:6,2,9,5,12,8,7,4,11,19,13,21
第四次执行时，直接返回j=9
(2)一开始执行HOARE-PARTITION时，i<j，因为，一开始A的数组大小为2，所以是正确的。
在循环过程中i只会增长，j只会递减，并且在while循环中，一旦i>=j循环就会退出。因此不会越界。
(3)第一个内层循环，j--最多减少到p,因为A[p]=x，所以第一个内层循环不得不终止，所以p<=j.
第一个内层循环，j--如果只循环了一次就终止，那么有A[r]=x,所以A[p]=A[r]=x 所以子数组内只有一个元素，这与题目
假设不符，所以第一个内层循环要循环2次，j=r-1<r 所以p<=j<r
(4)第一个内层循环的作用是找到数组右半部分小于主元的位置j.第二个内层循环的作用是找到数组左半部分大于主元的位置i
然后位置j的元素A[j]和位置i的元素A[i]互换，这样循环数次后，左半部分都小于主元，右半部分都大于主元，完成了划分。
(5)HOARE-QUICK-SORT的golang实现
package main
import (
"fmt"
)
// QuickSortInterface 满足快速排序的接口
type QuickSortInterface interface {
Get(i int) int
Swap(i int, j int)
}
// Partition 分解重排步骤
func HoarePartition(a QuickSortInterface, p int, r int) int {
x := a.Get(p)
i := p - 1
j := r + 1
for {
for {
j--
if a.Get(j) <= x {
break
}
}
for {
i++
if a.Get(i) >= x {
break
}
}
if i < j {
a.Swap(i, j)
} else {
return j
}
}
a.Swap(i+1, r)
return i + 1
}
func HoareQuickSort(a QuickSortInterface, p int, r int) {
if p < r {
q := HoarePartition(a, p, r)
HoareQuickSort(a, p, q)
HoareQuickSort(a, q+1, r)
}
}
type QuickSortSlice []int
func (a QuickSortSlice) Get(i int) int {
return a[i]
}
func (a QuickSortSlice) Swap(i int, j int) {
a[i], a[j] = a[j], a[i]
}
func main() {
a := QuickSortSlice{13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11}
HoareQuickSort(a, 0, 11)
fmt.Println(a)
}
7.2
答:
(1).运行时间会是O(n^2)
(2).修改后的golang代码为:
func Partition_(a QuickSortInterface, p int, r int) (int, int) {
x := a.Get(r)
i := p - 1
k := 0
for j := p; j < r; j++ {
if a.Get(j) < x {
i++
a.Swap(i, j)
a.Swap(i, i-k)
} else if a.Get(j) == x {
k++
i++
a.Swap(i, j)
}
}
a.Swap(i+1, r)
return i - k, i + 2
}
(3)golang实现:
package main
import (
"fmt"
"math/rand"
"time"
)
// QuickSortInterface 满足快速排序的接口
type QuickSortInterface interface {
Get(i int) int
Swap(i int, j int)
}
// Partition 分解重排步骤
func Partition_(a QuickSortInterface, p int, r int) (int, int) {
x := a.Get(r)
i := p - 1
k := 0
for j := p; j < r; j++ {
if a.Get(j) < x {
i++
a.Swap(i, j)
a.Swap(i, i-k)
} else if a.Get(j) == x {
k++
i++
a.Swap(i, j)
}
}
a.Swap(i+1, r)
return i - k, i + 2
}
func RandomPartition_(a QuickSortInterface, p int, r int) (int, int) {
rand.Seed(time.Now().UnixNano())
n := p + rand.Intn(r-p)
a.Swap(n, r)
return Partition_(a, p, r)
}
func QuickSort_(a QuickSortInterface, p int, r int) {
if p < r {
q, t := RandomPartition_(a, p, r)
QuickSort_(a, p, q)
QuickSort_(a, t, r)
}
}
type QuickSortSlice []int
func (a QuickSortSlice) Get(i int) int {
return a[i]
}
func (a QuickSortSlice) Swap(i int, j int) {
a[i], a[j] = a[j], a[i]
}
func main() {
a := QuickSortSlice{13, 19, 9, 5, 11, 12, 8, 7, 4, 11, 21, 2, 11, 6, 11}
//q, t := Partition(a, 0, 14)
QuickSort_(a, 0, 14)
//fmt.Println(q, t)
fmt.Println(a)
}
7.3
答：(a) E(Xi) =1/n
(b) 对于这么一个等式可以这么理解：求随机快速排序的期望运行时间就是对于每个随机的主元，求他们的期望运行时间之和。假设随机选择了主元Xi之后，子数组分为[1-(i-1)],[i+1,n]这两部分。并且每次分解的步骤会有O(n)的时间复杂度。
(c) 由于推导过程打字很麻烦，用手写代替：
(d)证明过程:
(e)
7.4
答:(b).如果原始的数组已经是排好序的，那么TAIL-RECURSIVE-QUICKSORT的栈深度为O(n).
因为此时，右子数组的大小为0，所以在while循环被打破前，会有n-1次的递归调用。
(c)伪代码：
while p < r do
q = PARTITION(A,p,r)
if(q < math.floor((r-p)/2)){
MODIFIED-TAIL-RECURSIVE-QUICKSORT(A,p,q-1)
p = q+1
}else{
MODIFIED-TAIL-RECURSIVE-QUICKSORT(A,q+1,r)
r = q - 1
}
end while
