Question

7-1 Hoare 划分的正确性

a）

A = {13 19 9 5 12 8 7 4 11 2 6 21}

==> A = {6 19 9 5 12 8 7 4 11 2 13 21}

==> A = {6 2 9 5 12 8 7 4 11 19 13 21}

==> A = {4 2 9 5 12 8 7 6 11 19 13 21}

==> A = {4 2 5 9 12 8 7 6 11 19 13 21}

==> A = {2 4 5 9 12 8 7 6 11 19 13 21}

==> A = {2 4 5 6 12 8 7 9 11 19 13 21}

==> A = {2 4 5 6 7 8 12 9 11 19 13 21}

==> A = {2 4 5 6 7 8 9 12 11 19 13 21}

==> A = {2 4 5 6 7 8 9 12 11 13 19 21}

b) 自己写的，很乱，凑合看吧

主要证明以下几点：

（1）do repeat j<-j-1 until A[j]<=x

这个 repeat 中，第一次执行 L6 时 p<=j<=r，最后一次执行 L6 时 p<=j<=r

证明：

1.第一次执行 L6 时 p<=j<=r。为了区分，j'=j-1，L6 中的 j 用 j'表示。

第一次进入 while 循环时，j=r+1，j'=r，满足 p<=j<=r。

若不是第一次进入 while 循环，j<=r 且 j>p。因为如果 j=p，在上一次 while 循环中 L9 的 if 不能通过，已经 return 了。因此 p<=j<r-1，满足 p<=j<=r。

2.最后一次执行 L6 时 p<=j<=r，即要证明在 A[p..r]中存在 j'满足 j'<=j 且 A[j]<=x

若第一次进入 while 循环，j'=p 满足条件

若不是第一次进入 while 循环，在上一次 while 循环中交换过去的那个元素满足条件

（2）do repeat i<i+1 until A[i]>=x

这个 repeat 中，第一次执行 L8 时 p<=i<=r，最后一次执行 L8 时 p<=i<=r

证明：证明方法与（1）类似

c) 根据 b 可知返回值 p<=j<=r，这里只需证明 j!=r

若 A[r]>x,L5 和 L6 的循环不会在 j=r 时停止，因此返回值 j!=r

若 A[r]<=x，只有在第一次进入 while 循环时，L5 和 L6 的循环在 j=r 时停止。因为是第一次进入 while 循环，A[i]=A[p]=x，L7 和 L8 的循环会在 i=p 时停止。显然会第二次进入 while 循环，此时 j<r，因此返回值 j!=r

d) 题目写错了，应该是 A[p..j]中的每个元素都小于或等于 A[j+1..r]中的每个元素

结束时，A[p..i-1]中的元素都小于 x，A[j+1..r]中的元素都大于 x，命题得证

e)

```c++
int Hoare_Partition(int A, int p, int r)
{
int x = A[p], i = p - 1, j = r + 1;
while(true)
{
do{j--;}
while(A[j] > x);
do{i++;}
while(A[i] < x);
if(i < j)
swap(A[i], A[j]);
else return j;
Print(A, 12);
}
}
void Hoare_QuickSort(int A, int p, int r)
{
if(p < r)
{
int q = Hoare_Partition(A, p, r);
Hoare_QuickSort(A, p, q-1);
Hoare_QuickSort(A, q+1, r);
}
}

### 7-2 对快速排序算法的另一种分析 

a)

       1 + 2 + …… + n     n + 1
E[Xi] = -------------------- = -------
        n         2

b) 后面几题表示完全看不懂

### 7-3 Stooge 排序

```c++
void Stooge_Sort(int *A, int i, int j)  
{  
  if(A[i] > A[j])  
    swap(A[i], A[j]);  
  if(i + 1 >= j)  
    return;  
  k = (j - i + 1) / 3;  
  Stooge_Sort(A, i, j-k);  
  Stooge_Sort(A, i+k, j);  
  Stooge_Sort(A, i, j-k);  
}

以下内容转 http://blog.csdn.net/zhanglei8893

a）对于数组 A[i...j]，STOOGE-SORT 算法将这个数组划分成均等的 3 份，分别用 A, B, C 表示。

第 6-8 步类似于冒泡排序的思想。它进行了两趟：

第一趟的第 6-7 步将最大的 1/3 部分交换到 C

第二趟的第 8 步将除 C 外的最大的 1/3 部分交换到 B

剩余的 1/3 位于 A，这样的话整个数组 A[i...j]就有序了。

b）比较容易写出 STOOGE-SORT 最坏情况下的运行时间的递归式

T(n) = 2T(2n/3)+Θ(1)

由主定律可以求得 T(n)=n^2.71

c）各种排序算法在最坏情况下的运行时间分别为：

插入排序、快速排序：Θ(n^2)

堆排序、合并排序：Θ(nlgn)

相比于经典的排序算法，STOOGE-SORT 算法具有非常差的性能，这几位终生教授只能说是浪得虚名了^_^

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

a)

```c++
void QuickSort2(int *A, int p, int r)
{
while(p < r)
{
int q = Partition(A, int p, r);
QuickSort2(A, p, q-1);
p = q + 1;
}
}

b) A = {1, 2, 3, 4, 5, 6}
c)

```c++
void QuickSort3(int *A, int p, int r)
{
  while(p < r)
  {
    int q = Partition(A, int p, r);
    if(r-q > q-p)
    {
      QuickSort3(A, p, q-1);
      p = q + 1;
    }
    else
    {
      QuickSort3(A, q+1, r);
      r = q - 1;
    }
  }
}

7-5 “三数取中”划分

a)n 个数任意取三个不同的数的取法共有 C(3,n) 种

若要 x=A'[i]，必须在 A'[1..i-1]中取一个数，在 A'[i+1..n]中取一个数取法共(i-1)*(n-i)

    (i-1) * (n-i)   6 * (i-1) * (n-i)
pi = --------------- = -------------------
     C(3,n)     n * (n-1) * (n-2)

b) 在一般实现中，pi=1/n。

n->正无穷时，极限为 0。

在这种实现中，当 i=(n+1)/2 时，

    3(n-1)
pi = ---------，当 n->正无穷时，极限为 0
    2n(n-2)

c) 遇到这种数学题就没办法了，哎，以前数学没学好

d) 不会求

附自己写的程序

7-6 对区间的模糊排序

见 算法导论 7-6 对区间的模糊排序