第二章 分治法（ Divide and Conquer)
—— ―分”而治之
2.1 一般方法
对大规模问题的求解
利用分治法求解大规模问题
Q q 2
q k
q 1
子 问 题
.,,
a 2
a k
a 1
子 问 题 求 解
.,,
问 题
A
子 结 果合 并分 解逐 步 细 化 的 过 程
1.分治策略基本思想当问题的规模较大而无法直接求解时，将整个问题分成若干个小问题，然后 分而治之 。
可用递归过程描述。
一般情况下，子问题与原始问题,同质”
算法 2.1 分治策略的抽象化控制
procedure DANDC(p,q)
global n.A(1:n);
integer m,p,q; //1≤p≤q≤n //
if SMALL(p,q)
then return(G(p,q))
else
m←DIVIDE(p,q) //p ≤m ＜ q//
return(COMBINE(DANDC(p,m),
DANDC(m+1,q)))
endif
end DANDC
注：
k=2,二分 是最常用的分解策略；
SMALL(p,q),布尔函数，判断输入规模 q-p+1是否足够小而无需再进一步分就可求解；
G(p,q),当 SMALL(p,q)为真时，
对输入规模为 q-p+1的子问题求解；
DIVIDE(p.q),当规模 q-p+1还较大时，对规模为 q-p+1的子问题进一步分解，返回值为 [p,q]区间进一步的 分割点 ；
COMBINE(x,y),子结果的合并函数，将区间 [p,m]和 [m+1,q]上的子问题的解合并成区间 [p,q]上的
“较完整”的解。当 p=1,q=n时，
就得到整个问题的解。
2,分治策略的抽象化控制过程
DANDC的计算时间若所分成的两个子问题的规模大致相等，则 DANDC总的计算时间可用递归关系式表示如下：
g(n) n足够小
T(n) =
2T(n/2) + f(n) 否则注：
T(n),表示输入规模为 n的 DANDC计算时间
g(n),表示对足够小的输入规模直接求解的计算时间
f(n),表示 COMBINE对两个子区间的子结果进行合并的时间
（该公式针对具体问题有各种不同的变形）
2.2 二分检索（折半查找）
1,问题的描述已知一个按 非降次序 排列的元素表 a1,
a2,…,a n，判定某给定的元素 x是否在该表中出现。
若是，则找出 x在表中的位置并返回其所在位置的下标
若非，则返回 0值。
问题的 形式描述,
I=(n,a1,a2,…,a n,x)
问题分解：选取下标 k，由此将 I分解为 3个子问题：
I1=(k-1,a1,a2,…,a k-1,x)
I2=(1,ak,x)
I3=(n-k,ak+1,a2,…,a n,x)
对于 I2，若 ak=x，则有解 k，对 I1,I3不用再求解；否则，
若 x<ak，则只在 I1中求解，对 I3不用求解；
若 x>ak，则只在 I3中求解，对 I1不用求解；
对 I1,I3的求解可 再次 采用分治方法求解
2,二分检索二分检索：每次选取 中间元素 的下标算法 2.3 二分检索
procedure BINSRCH(A,n,x,j)
integer low,high,mid,j,n;
low← 1; high← n;
while low≤high do
mid ←
case
:x<A(mid):high←mid -1
:x>A(mid):low ←mid+1
:else:j←mid;return
endcase
repeat
j←0
end BINSRCH
h i g h ) / 2( l o w?
注,
给定一个按非降次序排列的元素数组 A(1:n),n≥1,
判断 x是否出现。
若是，置 j，使得 x=A(j)
若非,j=0
例 2.1：设 A(1:9)=(-15,-6,0,7,9,23,54,82,101)
在 A中检索 x=101,-14,82。执行轨迹见下表 1
表 1 运行轨迹示例
x=101 x=-14 x=82
low high mid low high mid low high mid
1 9 5 1 9 5 1 9 5
6 9 7 1 4 2 6 9 7
8 9 8 1 1 1 8 9 8
9 9 9 2 1 找不到 找到找到成功 的检索 不成功 的检索 成功 的检索定理 2.1 过程 BINSRCH(A,n,x,j)能正确运行证明：
1）在具体指定 A中的数据元素及 x的数据类型后，算法中的所有运算都能按要求正确运行 ——即首先满足 确定性 和 能行性
2）终止性算法初始部分置 low←1,high←n
① 若 n=0，不进入循环,j置 0，算法终止
② 否则，进入循环，计算 mid,
或 x=A(mid),j置为 mid，算法终止；
或 x<A(mid)，置 high←mid -1，搜索范围实际缩小为 [low,mid-1]，
进入下次循环，对 [mid+1,high]区间不做进一步搜索；
或 x>A(mid)，置 low←mid+1,进入下次循环；搜索范围实际缩小为 [mid+1,high]，对 [low,mid-1]区间不做进一步搜索；
因 low,high,mid都是 整型 变量，故按照上述规则，在 有限步 内，或找到某个 mid，有 A(mid) = x；或变得 low>high，在 A中没有找到任何元素等于 x，算法终止。
3,性能分析
1）空间特性
n+5个空间位置 (A,x,j,mid,low,high)——О(n)
2) 时间特性区分以下情况进行分析
成功检索,指所检索的 x恰好在 A中出现。
由于 A中共有 n个元素，故成功检索恰好有 n种可能的情况
不成功检索,指 x不出现在 A中。
根据取值，不成功检索共有 n+1种可能的情况（ 取值区间 ）：
x<A(1) 或 A(i)<x<A(i+1),1≤i<n -1 或 x>A(n)
成功 /不成功检索的 最好情况,执行步数最少，计算时间 最短
成功 /不成功检索的 最坏情况,执行步数最多，计算时间 最长
成功 /不成功检索的 平均情况,一般情况下计算时间的 平均值实例分析（例 2.1）
运算的频率计数
1,while循环体外语句的频率计数为 1
2,集中考虑 while循环中 x与 A
中元素的 比较 运算
——其它运算的频率计数与比较运算相同的数量级
3,case语句的分析,假定只需 一次 比较就可确定 case
语句控制是三种情况的哪一种。
procedure BINSRCH(A,n,x,j)
integer low,high,mid,j,n;
low← 1; high← n;
while low≤high do
mid ←
case
:x<A(mid):high←mid -1
:x>A(mid):low ←mid+1
:else:j←mid;return
endcase
repeat
j←0
end BINSRCH
h i g h ) / 2( l o w?
实例分析（例 2.1）
查找每个元素所需的元素比较次数统计如下：
A ⑴ ⑵ ⑶ ⑷ ⑸ ⑹ ⑺ ⑻ ⑼
元素 -15 -6 0 7 9 23 54 82 101
成功检索 比较次数 3 2 3 4 1 3 2 3 4
不成功检索 比较次数 3 3 3 4 4 3 3 3 4 4
成功检索最好,1次最坏,4次平均,（ 3+2+3+4+1+3+2+3+4） /9≈ 2.77次
不成功检索最好,3次最坏,4次平均,(3+3+3+4+4+3+3+3+4+4)/10 = 3.4次二元比较树算法执行过程的主体是 x与一系列中间元素 A(mid)比较 。可用一棵二元树描述这一过程，称为 二元比较树
结点,分为 内结点 和 外结点 两种
内结点,· 代表一次 元素比较
· 用 圆形 结点表示
· 存放一个 mid值 (下标 )
· 代表 成功检索 情况
外结点,· 用方形结点表示，
· 表示 不成功检索 情况
路径,代表检索中元素的比较序列 例 2.1的二元比较树
5
2 7
1 3 6
8
4
9
二元比较树的查找过程
若 x在 A中出现，则算法的执行过程在一个圆形的 内结点 处结束
若 x不在 A中出现，则算法的执行过程在一个方形的 外结点 处结束注：外结点不代表元素的比较，因为比较过程在该外结点的 上一级 的内结点处结束。
5
2 7
1 3 6
8
4
9
例 2.1的二元比较树定理 2.2 若 n在区域 [2k-1,2k)中，则对于 一次成功的检索,
BINSRCH至多做 k次比较；对于 一次不成功的检索,
或者做 k-1次比较，或者做 k次比较。
证明要点：
二分检索中，每次 mid取中值，故其二元比较树是一种,结点平衡,的树，
★ 当 2k-1≤n< 2k时,结点分布 情况为：
内结点,1至 k级外结点,k级或 k+1级，
★ 外部结点在相邻的两级上 ——最深一层或倒数第 2层
比较过程：
成功检索在内结点处结束，不成功检索在外结点处结束
成功检索在 i级的某个内结点终止时，所需要的元素比较次数是 i
不成功检索在 i级的外部结点终止所需的元素比较次数是 i-1
BINSRCH的计算复杂度
n∈ [2k-1,2k)
k≈logn
1）外结点在最末的两级上，故不成功检索的最好、
最坏和平均情况的计算时间均为
2）最好情况下，成功检索的计算时间为最坏情况下，成功检索的计算时间为
Θ (lo gn )
Θ(1)
Θ (lo gn )
3）平均情况下的成功检索的计算时间利用 外部结点和内部结点到根距离和之间的关系 进行推导。
记，
由根到所有内结点的距离之和称为 内部路径长度,记为 I；
由根到所有外部结点的距离之和称为 外部路径长度,记为 E。
则有,E=I+2n · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ①
记，
U(n)是平均情况下不成功检索的计算时间，则
U(n) = E/(n+1) · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ②
S(n)是平均情况下成功检索的计算时间，则
S(n) = I/n + 1 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ③
由 ① ② ③得,
S(n) = (1+1/n)U(n) -1
当 n→∞,S(n) ∝ U(n),而 U(n) =
所以 S(n) =
Θ (lo gn )
Θ (lo gn )
成功检索最好 平均 最坏
Θ(1) Θ(logn) Θ(logn)
不成功检索最好 平均 最坏
Θ(logn) Θ(logn)Θ(logn)
4,以比较为基础检索的时间下界问题,设 n个元素的有序表 A(1:n),A(1)< A(2) < …< A(n) 。检索一给定元素 x是否在 A中出现。
问：是否预计还存在有以 元素比较 为基础的另外的检索算法，它在最坏情况下比二分检索算法在计算时间上有 更低 的数量级?
以比较为基础的算法,假定算法中只允许进行元素间的 比较,而不允许对它们实施其它运算。
内结点,表示一次元素的比较，并代表 成功检索 情况。每棵比较树中恰好含有 n个内结点，分别与 n个不同 i值相对应；
外结点,代表不成功检索情况。每棵比较树中恰好有 n+1个外结点分别与 n+1中不成功检索情况相对应。
分析：任何以比较为基础的检索算法，其执行过程都可以用二元比较树 来描述。
以比较为基础 的 有序检索 问题最坏情况的 时间下界定理 2.3 设 A(1:n)含有 n(n≥1) 个不同的元素，且有
A(1) < A(2) < …< A(n)
又设，用以比较为基础的算法去判断给定的 x是否有则，最坏情况下，任何这样的算法所需的最小比较次数 FIND(n)
有：
n):A ( 1x?
1)l o g ( nF I N D ( n )
证明：
① 从模拟求解检索问题算法的比较树可知,FIND(n)不大于 树中由根到一个叶子的最长路经的距离。
② 在所有的二元比较树中必定有 n个内结点分别与 x在 A中的 n中可能的出现相对应。
③ 如果一棵二元树的所有内结点所在的级数小于或等于 k，则该树中最多有 2k-1个内结点。
故,n≤2 k-1,即
1)l o g ( nkF I N D ( n )
结论
1）任何一种以比较为基础的有序检索算法，在 最坏情况 下的计算时间都 不低于 Ο(logn)。因此,不可能存在最坏情况比二分检索数量级还低的算法。
2）二分检索是解决检索问题的 最优 的 最坏情况 算法
2.3 找最大和最小元素查找问题：
1) 在元素表中确定某给定的元素的位置或判定其不出现：二分检索，顺序查找
2) 在元素表单独或同时找出其中的最大和
（或）最小
3) 在元素表找出其中第一小（大）和第二小
（大）元素
4) 找元素表中的第 k小元素：排序或选择等等本节问题：在元素表同时找出最大元素和最小元素问题描述,给定含有 n个元素的集合（以数组 A表示），找出其中的最大和最小元素。
二种算法的比较：
迭代算法递归算法
1,直接找最大和最小元素算法 2.5 直接找最大和最小元素
procedure STRAITMAXMIN(A,n,max,min)
//将 A中的最大值置于 max，最小值置于 min//
Integer i,n
max←min←A(1)
for i←2 to n do
if A(i) > max then
max←A(i)
endif
if A(i) < min then
min←A(i)
endif
repeat
end STRAITMAXMIN
算法的性能：
只考虑算法中的 比较运算,以此代表算法的执行特征；
该算法最好、最坏、
平均情况下均需要做
2（ n-1） 次元素比较
STRAITMAXMIN算法的一种简单改进形式,
procedure STRAITMAXMIN1(A,n,max,min)
integer i,n
max←min←A(1)
for i←2 to n do
if A(i) > max then max←A(i) endif
else if A(i) < min then min←A(i) endif
repeat
end STRAITMAXMIN1
这使得，
最好情况,按 递增次序 排列，元素比较次数为 n-1次
最坏情况,按 递减次序 排列，元素比较次数为 2(n-1)次
平均情况,元素比较次数为 3(n-1)/2次
2,分治求解策略记问题的一个实例为：
I = (n,A(1),…,A(n))
采用二（等）分法将 I分成两个子集合处理
I1 = (,A(1),…,A( ))，和
I2 = (n-,A( +1),…,A(n))
则有，
MAX(I) = max(MAX(I1),MAX(I2))
MIN(I) = min(MIN(I1),MIN(I2))
MAX(I)和 MIN(I)分别代表 I中元素的最大者和最小者采用 递归 的设计策略，得到以下算法：
n/2n/2
n/2n/2
3,找最大最小元素的递归求解算法算法 2.6 递归求取最大和最小元素
procedure MAXMIN(i,j,fmax,fmin)
//A(1:n)是含有 n个元素的全局数组，参数 i,j是整数,1≤i,j≤n,代表当前的查找区间 //
//该过程把 A(i:j)中的最大和最小元素分别赋给 fmax和 fmin //
integer i,j;global n,A(1:n)
case
:i=j,fmax←fmin←A(i) // 只有一个元素
:i=j-1:if A(i)<A(j) then fmax←A(j);fmin←A(i)
else fmax←A(i);fmin←A(j) // 两个元素的情况
endif
:else,mid← // 取中，并在两个子区间上作递归调用
call MAXMIN(i,mid,gmax,gmin)
call MAXMIN(mid +1,j,hmax,hmin)
fmax←max(gmax,hmax); fmin←min(gmin,hmin)
end case
end MAXMIN
j)/2(i?
MAXMIN过程的初始调用,
MAXMIN（ 1,n,fmax,fmin）
数组 A是全局数组
fmax,fmin带出 A(1:n)中的最大和最小元素例：在 A(1:9) = (22,13,-5,-8,15,60,17,31,47)上执行算法 2.6
每个结点内的值分别是：
i,j,fmax,fmin
递归调用递归调用分解过程递归调用的返回区间划分将一直进行到只含有 1个或 2个元素时为止，然后求子解，并返回
MAXMIN过程的性能分析 ——仅考虑算法中的 比较运算
0 n=1
T(n) = 1 n=2
n>2
当 n是 2的幂时 (n=2k),化简上式有，
T(n)=2T(n/2) +2
=2(2T(n/4) + 2) + 2
…
=2k-1T(2) +
=2k-1+2k-2
=3n/2-2
2)n / 2T()n / 2T(
1ki1 i2
性能比较
1）与 STRAITMAXMIN算法相比，比较次数减少了 25%
（ 3n/2-2,2n-2)。
已经达到了以 元素比较为基础 的找最大最小元素的算法计算时间的 下界,
2）存在的问题 ——递归调用造成：
空间占用量大有 级的递归，入栈参数：
i,j,fmax,fmin和返回地址五个值。
时间可能不比预计的理想如果元素 A(i)和 A(j)的比较与 i和 j的比较在 时间 上 相差不大 时，算法 MAXMIN不可取 。
22/3?n
1lo g?n
假设元素的比较与 i和 j的比较时间相同（整型数）。又设对 case语句调整，使得仅需一次 i和 j的比较就能够确定是哪种情况。
case
:i>=j-1:if A(i)<A(j) then fmax←A(j);fmin←A(i)
else fmax←A(i);fmin←A(j) // 两个元素的情况
endif
:else,?
记此时 MAXMIN的频率计数为 C(n),n=2k (k为正整数）。则有，
2 n<=2 (一次是 i和 j-1的比较，一次是 A(i)和 A(j)的比较 )
C(n) =
2C(n/2)+3 n>2
化简得，
C(n) = 2C(n/2) + 3
= …
= 5n/2 -3
按照同样的假设，重新估算 STRAITMAXMIN算法的比较次数为,3(n-1)。
STRAITMAXMIN与 MAXMIN在计算时间上的差异越来越小
1/4 （ 25%） =>1/6（ 16.7%）
考虑 MAXMIN算法 递归调用的开销,此时 MAXMIN算法的效率可能还不如 STRAITMAXMIＮ算法。
结论：如果 A中的元素间的比较代价远比整型数
（下标）的比较 昂贵,则分治方法将产生一个 效率较高 的算法；
反之，可能仅得到一个 低效 的算法。
故，分治策略只能看成一个 较好的 但 并不总是成功的算法设计指导。
2.4 归并分类
1,分类问题 ——排序给定一 n个元素的集合 A，按照某种方法将 A中的元素按非降或非增次序排列。
分类：内排序，外排序常见内排序方法：冒泡排序插入排序归并排序快速排序堆排序
…
2,插入分类算法 2.7 插入分类
procedure INSERTIONSORT(A,n)
//将 A(1,n)中的元素按非降次序分类,n≥1//
A(0)← -∞//设置初始边界值
for j←2 to n do //A(1:j -1)已分类 //
item←A(j);i←j -1
while item<A(i) do //0≤i<j//
A(i+1)←A(i); i←i -1
repeat
A(i+1) ←item;
repeat
end INSERTIONSORT
i指示的是 j之前的一位，即当前已排序子表的最末一个元素的下标性能分析：
最坏 情况：输入数据按非增次序排列,每次 内层
while循环 执行 j次（ j=2,3,…,n) 。则有，
最好 情况：输入数据已按非降序排列，不进入
while循环，则最好情况下计算时间为 Ω(n)
)Θ ( n 2?
1 1 ) ) / 2( n ( nj
nj2
3.分治策略求解基本设计思想：将原始数组 A中的元素分成两个子集合,A1(1,)和 A2( +1,n)。分别对这两个子集合单独分类，然后将已分类的两个子序列 归并 成一个含有 n个元素的分类好的序列。
这样的一个分类过程称为 归并分类 。
n/2n/2
算法 2.8 归并分类
procedure MERGESORT(low,high)
//A(low:high)是一个全程数组,low和 high分别指示当前待分类区间的最小下标和最大下标，含有 high-low+1≥0 个待分类的元素 //
integer low,high
if low<high then //当含有 2个及 2个以上的元素时，作划分与递归处理 //
mid← //计算 中分点 //
call MERGESORT(low,mid) //在第一个子集合上分类 (递归 )//
call MERGESORT(mid+1,high) //在第二个子集合上分类 (递归 )//
call MERGE(low,mid,high) //归并已分类的两子集合 //
endif
end MERGESORT
h i g h ) / 2( l o w?
算法 2.9 使用辅助数组归并两个已分类的集合
procedure MERGE(low,mid,high)
//A(low,high)是一个全程数组,它含有两个放在 A(low,mid)和 A(mid+1,high)中的已分类的子集合,目标是将这两个已分类的集合归并成一个集合，并存放到 A(low,high)中 //
integer h,I,j,k,low,mid,high;//low≤mid＜ high//
global A(low,high);local B(low,high)
h←low;i←low; j←mid+1;
while h≤mid and j≤high do //当两个集合都没有取尽时,将较小的元素先存放到 B中 //
if A(h)≤A(j) then B(i) ←A(h);h←h+1 //如果前一个数组中的元素较小 //
else B(i) ←A(j); j←j+1 //如果后一个数组中的元素较小 //
endif
i← i+1
repeat
//处理尚有剩余元素的集合 //
if h>mid then for k←j to high do B(i) ←A(k);i←i+1; repeat
else for k←h to mid do B(i) ←A(k);i←i+1; repeat
endif
for k ←low to high do A(k) ←B(k) repeat //将已归并的集合复制到 A中 //
end MERGE
性能分析
1) 过程 MERGE的归并时间与两数组元素的总数成正比故可表示为,cn,n为元素数,c为某正常数
2) 过程 MERGESORT的分类时间用递推关系式表示如下,
a n=1,a是常数
T(n)=
2T(n/2)+cn n>1,c是常数化简,若 n=2k,则有,
T(n) =2(2T(n/4)+cn/2)+cn
= 4T(n/4) + 2cn =4T(2T(n/8) +cn/4) + 2cn
= …
=2kT(1)+kcn
=an+cnlogn //k=logn//
若 2k<n<2k+1,则有 T(n)≤T(2k+1)。
所以得,T(n) = Ο(nlogn)
递归调用一直进行到子区间仅含一个元素时为止归并分类示例
设 A=（ 310,285,179,652,351,423,861,254,450,520）
1）划分过程
310,285,179,652,351,423,861,254,450,520
310,285,179,652,351 423,861,254,450,520
310,285,179 652,351
310,285 179
310 285
652 351
423,861,254 450,520
423,861 254
423 861
450 520
2）归并过程首先进入左分枝的划分与归并。
第一次归并前的划分状态是：
（ 310 | 285 | 179 | 652,351 | 423,861,254,450,520）
第一次归并：（ 285,310 | 179 | 652,351 | 423,861,254,450,520）
第二次归并：（ 179,285,310 | 652,351 | 423,861,254,450,520）
第三次归并：（ 179,285,310 |351,652 | 423,861,254,450,520）
第四次归并：（ 179,285,310,351,652 | 423,861,254,450,520）
进入右分枝的划分与归并过程
（略）
3）用树结构描述归并分类过程
4,归并分类算法的改进
1）算法 2.8存在的问题
递归层次太深在 MERGESORT的执行过程中，当集合仅含有两个元素时，仍要进一步做递归调用，直至每个集合仅含有一个元素时才退出递归调用。
在集合含有仅相当少的元素时，较深层次的递归调用使得时间 过多地消耗 在处理递归上。
元素在数组 A和辅助数组 B之间的频繁移动每次归并，都要首先将 A中的元素移到 B中，在由 B复制到 A的对应位置上。
2）改进措施
针对递归层次问题采用能 在小规模集合 上有效工作的其它算法，直接对小规模集合处理。
如 INSERTIONSORT算法
针对元素频繁移动问题采用一个称为 链接信息数组 LINK（ 1,n） 的数据结构，
记录归并过程中 A中的元素相对于其排序后在分类表中 位置坐标的链接关系。
LINK(i)取值于 [1,n]，是指向 A的元素的指针：在分类表中它指向下一个元素在 A中的位置坐标。
例：
LINK (1) (2) (3) (4) (5) (6) (7) (8)
6 4 7 1 3 0 8 0
该表中含有 两个子表,0表示表的结束。
设置 表头指针 Q和 R分别指向两个子表的起始处：
Q=2,R=5；
则有，
表 1,Q(2,4,1,6),经过分类后有,A(2)≤ A(4) ≤ A(1) ≤ A(6)
表 2,R(5,3,7,8),同样有,A(5)≤ A(3) ≤ A(7) ≤ A(8)
链接信息表在归并过程中的应用,
将归并过程中元素在 A和 B之间移动的过程变成更改 LINK
所指示的链接关系，从而避免移动元素的本身。
分类表可以通过 LINK的表头指针和读取 LINK中的链接关系取得。
改进后的归并分类模型算法 2.10 使用链接信息数组的归并分类模型
procedure MERGESORT1(low,high,p)
//利用链接信息数组 LINK(1:n)将全程数组 A(low:high)按非降次序分类。 LINK中值表示按分类次序给出
A下标的表，并把 p置于该表的开始处 //
global A(low:high),LINK(low,high)
if high-low+1<16 //当集合中的元素个数足够少 (<16)时，采用更有效的小规模集合上的分类算法直接分类 //
then call INSERTSORT1(A,LINK,low,high,p) //算法 2.7的改型 //
else mid←
call MERGESORT1(low,mid,q) //返回 q表 //
call MERGESORT1(mid+1,high,r) //返回 r表 //
call MERGE1(q,r,p) //将表 q和表 r归并成表 p//
endif
end MERGESORT1
h i g h ) / 2( l o w?
算法 2.11 使用链接表归并已分类的集合
procedure MERGE1(q,r,p)
//q和 r是全程数组 LINK(1:n)中两个表的指针。归并这两个表，得到一个由 p所指示的新表。此表将
A中的元素按非降次序分类。 LINK(0)被定义 //
global n,A(1:n),LINK(1:n)
local integer i,j,k
i←q;j←r;k←0 //新表在 LINK(0)处开始 //
while i≠0 and j≠0 do //当两表均非空时 //
if A(i) ≤ A(j) //找较小的关键字 //
then LINK(k) ←i;k←i;i←LINK(i) //加一个新关键字到表中 //
else LINK(k) ←j;k←j;j←LINK(j) //加一个新关键字到表中 //
endif
repeat
if i=9 then LINK(k) = j
else LINK(k) = i
endif
end MERGE1
MERGESORT1 的调用
在初次调用时，待分类的 n个元素放于 A(1:n)中。
LINK(1:n)初始化为 0；
初次调用,call MERGESORT1(1,n,p)
p作为按分类次序给出 A中元素的指示表的指针。
3）改进归并分类算法示例设元素表：（ 50,10,25,30,15,70,35,55）
采用 MERGESORT1对上述元素表分类（不做小规模集合的单独处理）
下表给出在每一次调用 MERGESORT1结束后,LINK数组的变化情况。
在上表的最后一行,p=2返回，得到链表（ 2,5,3,4,7,1,8,6）
即,A(2)≤ A(5)≤ A(3)≤ A(4)≤ A(7)≤ A(1)≤ A(8)≤ A(6)
5,以比较为基础分类的时间下界
1.分类的“实质”
给定 n个记录 R1,R2,…,R n,其相应的关键字是 k1,k2,…,k n。
分类就是确定 1,2,…,n 的一种排列 P1,P2,…P n,使得记录的关键字满足以下非递减（或非递增）排列关系
kP1≤ kP2≤ … ≤ kPn
从而使 n个记录成为一个按关键字有序的序列：
{ RP1,RP2,…,R Pn }
2,以关键字比较为基础的分类算法的时间下界最坏情况下的时间下界为,Ω(nlogn)
利用 二元比较树 证明。
假设参加分类的 n个关键字 A(1),A(2),?,A(n) 互异。任意两个关键字的比较必导致 A(i)<A(j)或 A(i)>A(j)的结果。
以二元比较树描述元素间的比较过程：
若 A(i)<A(j)，进入下一级的 左分支
若 A(i)>A(j)，进入下一级的 右分支算法在 外部结点 终止。
从根到某外结点的 路径 代表某个特定输入情况下一种唯一的 分类排序序列 。 路径长度 表示生成该序列代表的分类表所需要的 比较次数。 而 最长的路径 代表算法在最坏情况下的执行情况，该路径的长度即是算法在最坏情况下所作的比较次数。
故，以比较为基础的分类算法的 最坏情况下界 等于该算法对应的比较树的 最小高度 。
初始集合中的元素因顺序不同，将导致排序过程走不同的分支
① 由于 n个关键字有 n!种可能的排列，所以分类二元比较树中将有
n!个 外部结点,每个外部结点代表一种特定的排列，该排列对应于某种特定输入情况下的分类序列。
② 设一棵二元比较树的所有 内结点 的级数均小于或等于 k，则该树中最多有 2k个外结点。
记算法在最坏情况下所作的比较次数为 T(n),则有 T(n)=k：生成外结点所代表的分类序列所需的比较次数等于该外结点所在的级数 -1；
根据①和②的分析，有：
n!≤2 T(n)
化简：
当 n>1时，有 n!≥n(n -1)(n-2)?( )≥(n/2) n/2
当 n≥4 时，有 T(n)≥(n/2)log(n/2)≥(n/4)logn
故，任何以比较为基础的分类算法的最坏情况的时间下界为：
Ω(nlogn)
n/2
1.划分与快速分类
快速分类是一种基于 划分 的分类方法；
划分,选取待分类集合 A中的某个元素 t，按照与 t的大小关系重新整理 A中元素，使得整理后 t被置于序列的某位置上，
而序列中所有在 t以前出现的元素均 小于等于 t，而所有出现在 t以后的元素均 大于等于 t。这一元素的整理过程称为划分 （ Partitioning）。
元素 t称为 划分元素 。
快速分类,通过 反复 地对待排序集合进行 划分 达到分类目的的分类算法。
2.5 快速分类划分过程（ PARTITION）的算法描述算法 2.2 用 A(m)划分集合 A(m:p-1)
procedure PARTITION(m,p)
integer m,p,i; global A(m:p-1)
v←A(m);i←m //A(m) 是划分元素 //
loop
loop i←i+1 until A(i)≥v repeat // i 由左向右移 //
loop p←p -1 until A(p)≤v repeat //p由右向左移 //
if i<p then
call INTERCHANGE(A(i),A(p))
else exit
endif
repeat
A(m)←A(p) ； A(p)←v // 划分元素在位置 p//
end PARTITION
A(p)被定义，但为一限界值，
不包含在实际的分类区间内。
pi
v v
注：
算法对集合 A(m:p-1)进行划分。并使用待划分区间的第一个元素 A(m)作为划分元素
A(p)不在划分区间内，但被定义，且 A(p） ≥ A(m)，用于限界例 2.5 划分实例
(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) i p
A,65 70 75 80 85 60 55 50 45 +∞ 2 9
|……………………………………|
A,65 45 75 80 85 60 55 50 70 +∞ 3 8
|…………………………|
A,65 45 50 80 85 60 55 75 70 +∞ 4 7
|………………|
A,65 45 50 55 85 60 80 75 70 +∞ 5 6
|……|
A,65 45 50 55 60 85 80 75 70 +∞ 6 5
|……………………|
A,60 45 50 55 65 85 80 75 70 +∞
划分元素定位于此交换划分元素经过一次,划分” 后，实现了对集合元素的调整：
以划分元素为界，左边子集合的所有元素均 小于等于 右边子集合的所有元素。
按同样的策略对两个子集合进行分类处理。当子集合分类完毕后，整个集合的分类也完成了。这一过程避免了子集合的归并操作。这一分类方法称为快速分类 。
2.快速分类算法
——一种通过反复使用划分过程 PARTITION实现对集合元素分类的算法。
算法 2.13 快速分类
procedure QUICKSORT(p,q)
//将数组 A(1:n)中的元素 A(p),…A(q) 按递增的方式分类。
A(n+1)有定义,且假定 A(n+1)←+ ∞//
integer p,q;global n,A(1:n)
if p<q then
j←q+1 //进入时,A(j)定义了划分区间 [p,q]的 上界,首次调用时 j=n+1
call PARTITION(p,j) //出口时,j带出此次划分后划分元素所在的 下标位置 //
call QUICKSORT(p,j-1) //对前一子集合递归调用
call QUICKSORT(j+1,q) //对后一子集合递归调用
endif
end QUICKSORT
3,快速分类分析
统计的对象：元素的 比较次数,记为,C(n)
两点假设
① 参加分类的 n个元素各不相同
② PARTITION中的划分元素 v是 随机 选取的（针对平均情况的分析）
随机选取划分元素,
在划分区间 [m,p-1]随机生成某一坐标,i←RANDOM(m.p -1)；
调换 A(m)与 A(i):v←A(i);A(i) ←A(m);i←m
作用：将随机指定的划分元素的值调换到 A(m)位置。算法主体不变。之后，仍从 A(m)开始执行划分操作。
递归层次
QuickSort(1,n)
QuickSort(1,j1-1) QuickSort(j1-1,n)
QuickSort(1,j21-1) QuickSort(j21+1,j1-1) QuickSort(j1-1,j22-1) QuickSort(j22+1,n)
n个元素参加划分和分类去掉 1个第一级的划分元素
n-1个元素参加划分和分类去掉 2个第二级的划分元素
n-3个元素参加划分和分类去掉 4个第三级的划分元素第一层第二层第三层设在任一级递归调用上，调用 PARTITION处理的所有元素总数为 r，则，初始时 r=n，以后的每级递归上，由于删去了上一级的划分元素，故 r比上一级至少 1：
理想情况,第一级少 1，第二级少 2，第三级少 4,… ；
最坏情况,每次仅减少 1（每次选取的划分元素刚好是当前集合中最小或最大者）
最坏情况分析
记 最坏情况 下的元素比较次数是 Cw(n)；
PARTITION一次调用中的元素比较数是 p-m+1,故每级递归调用上,PARTITION所做的比较总数为 O(r),r是任一级递归调用上 PARTITION所处理的元素总数。
最坏情况下（元素已有序），每级递归调用的元素总数仅比上一级少 1，故 Cw(n)是 r由 n到 2的累加和。
即,Cw(n)= = Ο(n2)?
nr
r
1
平均情况分析平均情况 是指集合中的元素以任意顺序排列，且任选元素作为划分元素进行划分和分类，在这些所有可能的情况下，算法执行性能的 平均值 。
设调用 PARTITION(m,p)时，所选取划分元素 v恰好是
A(m:p-1)中的第 i小元素（ 1≤i≤p -m）的概率相等。则经过一次划分，所留下的待分类的两个子文件恰好是 A(m:j-1)和
A(j+1:p-1)的概率是,1/(p-m),m≤j<p 。 记 平均情况 下的元素比较次数是 CA(n)； 则有，
其中，
n+1是 PARTITION第一次调用时所需的元素比较次数。
CA(0) = CA(1) = 0
nk AAnA knCkCnnC 11 ))()1((1)(
化简上式可得：
CA(n)/(n+1) = CA(n-1)/n + 2/(n+1)
= CA(n-2)/(n-1) + 2/n + 2/(n+1)
= CA(n-3)/(n-2)+2/(n-1)+2/n+2/(n+1)
= CA(1)/2+
由于所以得,CA(n)<2(n+1)loge(n+1) = Ο(nlogn)
13
/12
nk
k
)1(l o g/1 12
13
nk en xdx
nk
空间分析最坏情况下，递归的最大深度为 n-1.
需要栈空间,O(n)
使用一个迭代模型可以将栈空间总量减至 O(logn)
4,快速分类算法的迭代模型处理策略,每次在 Partition将文件 A(p:q)分成两个文件
A(p:j-1)和 A(j+1,q)后，先对其中 较小 的子文件进行分类。当小的子文件分类完成后，再对较大的子文件进行分类。
栈,需要一个栈空间保存目前 暂不分类 的较大子文件。并在较小子文件分类完成后，从栈中退出最新的较大子文件进行下一步分类。
栈空间需要量,O(logn)
算法的终止,当栈空时，整个分类过程结束。
算法 2.14 QuickSort2(p,q)
integer STACK(1:max),top //max=2
global A(1:n);local integer j
top←0
loop
while p<q do
j←q+1
call PARTITION(p,j);
if j – p < q – j //先对较小的子文件分类，并将规模较大的子文件入栈
then STACK(top+1)←j+1; STACK(top+2)←q; q←j -1
else STACK(top+1)←p; STACK(top+2)←j -1; p←j+1
endif
top←top+2 // 调整栈顶指针
repeat
if top=0 then return endif //如果栈为空，算法结束
q←STACK(top);p←STACK(top -1); top←top -2 //从栈中退出先前保存的较大的子文件
repeat
end QUICKSORT2
nlog
快速分类算法迭代模型的空间分析算法 2.14的最大空间是 O(logn)
推导：
设算法所需的最大栈空间是 S(n)，则有
1n 0
1n )2/)1((2)( nSnS
2.6 选择问题
1,问题描述在 n个元素的表 A(1:n)中确定第 k小元素,1≤k≤n 。
2,设计思路利用 PARTITION过程。在第一次划分后划分元素 v测定在 A(j)的位置上，则有 j-1个元素小于或等于 A(j)，且有 n-j个元素大于或等于 A(j)。此时，
若 k=j，则 A(j)即是第 k小元素；否则，
若 k<j，则 A(1:n)中的第 k小元素将出现在 A(1:j-1)中,
且仍是 A(1:j-1)中的第 k小元素；
若 k>j，则 A(1:n)中的第 k小元素将出现在 A(j+1:n)中，
但是 A(j+1:n)中的第 k-j小元素。
3,利用 PARTITION实现的选择算法
算法描述算法 2.15 找第 k小元素
procedure SELECT(A,n,k) //在数组 A(1:n)中找第 k小元素，并将之放在 A(k)中。 //
integer n,k,m,r,j;
m←1;r ← n+1;A(n+1) ←+∞ //A(n+1)被定义，并置为一大值，用于限界 //
loop //在进入循环时,1≤m≤k≤r≤n+1 //
j ←r //将剩余元素的最大下标加 1后置给 j //
call PARTITION(m.j) //返回 j,它使得 A(j)是第 j小的值 //
case
:k=j,return
:k<j,r←j //j是新的上界 //
:else,m←j+1 //k>j,j+1是新的下界 //
endcase
repeat
end SELECT
算法分析两点假设
① A中的元素 互异
② 随机选取 划分元素，且选择 A中任一元素作为划分元素的 概率相同分析
每次调用 PARTITION（ m,j),所需的元素比较次数是
Ο(j-m+1)。
在执行一次 PARTITION后，或者找到第 k小元素，或者将在缩小的子集 (A(m,k-1)或 A(k+1,j))中继续查找。缩小的子集的元素数将 至少 比上一次划分的元素数 少 1。
1) 最坏情况
SELECT的最坏情况时间是 Ο(n2)
最坏情况下的特例：
输入 A恰好使对 PARTITION的第 i次调用选用的划分元素是第 i小元素，
而 k=n。
此时，（区间下界） m随着 PARTITION的每一次调用而仅增加 1,j
保持不变。 PARTITION最终需要调用 n次。
则,n次调用的时间总量是
)())1(( 2
1
ni
n
2) 平均情况设 是找 A(1:n)中第 k小元素的平均时间。 是
SELECT的平均计算时间，则有并定义则有,T(n)≤R(n)。
nk
k
AnA nTnT
1
1 )()(
)(nTA
)}({m a x)( nTnR kAk?
)(nTkA
对 n个不同的元素，问题实例可能的 n!种不同情况，综合考查所得的平均值在所有可能的情况下，找所有可能的 k小元素某个特定的 k
定理 2.4 SELECT的平均计算时间 TA(n)是 Ο(n)
证明：
PARTITION的一次执行时间是 Ο(n)。 在随机等概率选择划分元素时，首次调用 PARTITION中划分元素 v刚好是 A中第 i
小元素的概率为 1/n,1≤ i≤ n。
则，存在正常数 c,c>0,有，
n≥2
且有，
n≥2
1 ) )(iTi)(nT(cn( n )T
nik
k
A
ki1
ik
An1
k
A
1 ) }(iRi)(nR{m a xcnR ( n )
nikki1kn
1
( i ) }R( i )R{m a xcn
1n
k
1n
1knk
n
1
划分元素 i<k,将在 i的后半部分求解划分元素 i>k,将在 i
的前半部分求解令 c≥R(1) 。利用 数学归纳法 证明，对所有 n≥2,有 R(n)≤4cn.
① 当 n=2时，由上式得：
② 假设对所有的 n,2≤n<m，有 R(n)≤4cn
③ 当 n = m时，有，
由于 R(n)是 n的非降函数，故当 m为偶数而 k=m/2，或当 m为奇数而
k=(m+1)/2时,取得极大值。因此，
若 m为偶数,则若 m为奇数,则由于 TA(n)≤R(n)，所以 TA(n)≤4cn。 故,TA(n)=Ο(n)
R ( 1 ) }m a x { R ( 1 ),212cR ( n )
4cn2.5c
( i) }R( i)R{m a xcm)( 1m
k
1m
1kmk
m1
nR
1m
m / 2
m2 R ( i)cmR ( m )?
1m
m / 2
m
8c 4 c micm
1m
1 ) / 2(m
m
2 R ( i )cmR ( m )?
1m
1 ) / 2(m
m
8c 4 c micm
( i)R( i)R 1n
k
1n
1kn
1 k m-1
1 m– k+1 m-1
4,最坏情况是 Ο(n)的选择算法
1）采用两次取中间值的规则精心选取划分元素首先，将参加划分的 n个元素分成 组，每组有 r个元素 (r≥1) 。（多余的 个元素忽略不计）
然后，对这 组每组的 r个元素进行分类并找出其中间元素 mi,1≤i≤,共得 个中间值。
之后，对这 个中间值分类，并找出其中间值 mm。
将 mm作为划分元素执行划分。
2）算法描述
n/r
n/rrn?
n/r
n/rn/r
n/r
例：设 n=35,r=7。
分为 n/r = 5个元素组：
B1,B2,B3,B4,B5；
每组有 7个元素。
B1-B5按照各组的 mi的非增次序排列。
mm = mi的中间值,1≤i≤5
由图所示有,
mm
中间值小于等于 mm的元素大于等于 mm的元素非降次序
B1 B2 B3 B4 B5
按照 mi的非降次序排列由于 r个元素的 中间值 是第 小元素。则，
至少有 个 mi小于或等于 mm；
至少有 个 mi大于或等于 mm。
故，至少有 个元素小于或等于（或大于或等于） mm。
当 r=5，则使用两次取中间值规则来选择 v=mm，可得到，
至少有 个元素小于或等于选择元素 v。
且至多有 个元素大于 v。
同理，至多有 0.7n+1.2个元素小于 v。
故，这样的 v可 较好 地划分 A中的 n个元素。
/2n / r1/2n / rn / r
2/n/r
2/r
/2n /rr/2
n/55.1
1,20,7 nn / 51,5n
算法 2.16 使用二次取中规则的选择算法的说明性描述
Procedure SELECT2(A,k,n)
//在集合 A中找第 k小元素
① 若 n≤r，则采用插入法直接对 A分类并返回第 k小元素
② 把 A分成大小为 r的 个子集合，忽略多余的元素
③ 设 M={m1,m2,…m } 是 子集合的中间值集合
④ v← SELECT2(M,,)
⑤ j← PARTITION(A,v)
⑥ case
:k=j,return(v)
:k<j,设 S是 A(1:j-1)中元素的集合 ; return(SELECT2(S,k,j-1))
:else,设 R是 A(j+1:n)中元素的集合 ; return(SELECT2(R,k-j,n-j))
endcase
end SELECT2
n/r
n/r
n/r2/n/r
n/r
2) 算法分析记 T(n)是 SELECT2所需的最坏情况时间对特定的 r分析 SELECT2:选取 r=5。
假定 A中的元素各不相同，则有
① 若 n≤r，则采用插入法直接对 A分类并返回第 k小元素 → Ο(1)
② 把 A分成大小为 r的 个子集合，忽略多余的元素 → Ο(n)
③ 设 M={m1,m2,…m r }是 子集合的中间值集合 → Ο(n)
④ v← SELECT2(M,,) → T(n/5)
⑤ j← PARTITION(A,v) → Ο(n)
⑥ case →T(3n/4),n ≥24
:k=j,return(v)
:k<j,设 S是 A(1:j-1)中元素的集合 ; return(SELECT2(S,k,j-1))
:else,设 R是 A(j+1:n)中元素的集合 ; return(SELECT2(R,k-j,n-j))
endcase
end SELECT2
n/r
n/r
n/r2/n/r
r为定值，记对 r个元素的直接排序的时间为“定值”
故有，
cn n ＜ 24,
T(n)＝
T(n/5)+T(3n/4)+cn n≥24
用归纳法可证：
T(n)≤20cn
故，在 r=5地情况下，求解 n个不同元素选择问题的算法
SELECT2的最坏情况时间是 Ο(n)。
当 A中的元素 不尽相同步骤⑤经 PARTITION调用所产生的 S和 R两个子集合中可能存在一些元素 等于 划分元素 v,可能导致 |S|或 |R|大于 0.7n+1.2。
改进：
方法一：将 A集合分成 3个子集合 U,S和 R，其中 U是由 A中所有与 v相同的元素组成,S是由 A中所有比 v小的元素组成,R则是 A中所有比 v大的元素组成。
同时步骤⑥更改：
case
:|S|≥k:return(SELECT2(S,k,|S|)
:|S|+|U|≥k:return(v)
:else,return(SELECT2(R,k-|S|-|U|,|R|))
endcase
从而保证 |S|+|R|≤0.7n+1.2 成立，故关于 T(n)的分析仍然成立。
T(n) = Ο(n)
方法二：选取其他的 r值进行计算特例：当 r=5,且 A中的元素不尽相同。假设其中有 0.7n+1.2个元素比 v小而其余的元素都等于 v的情况。
则，经过 PARTITION，在这些等于 v的元素中至多有一半可能在 S中，
故 |S|≤0.7n+1.2+(0.3n -1.2)/2=0.85n+0.6
同理,|R|≤0.85n+0.6
可得，此时步骤④和⑥所处理的元素总数将是
1.05n+0.6>n
不再是 线性 关系。故有 T(n)≠ Ο(n)
改进：
取 r=9。经计算可得，此时将有 个元素小于或等于 v，同时至少有 大于或等于 v。
则 当 n≥90 时,|S|和 |R|都至多为基于上述分析，有新的递推式：
n/92.5
72/6325.136/319/25.1)9/5.2(9/5.2 21 nnnnnnn
相等元素的一半n/92.5
故有，
c1n n＜ 90
T(n) ＝
T(n/9)+T(63n/72)+c1n n≥90
用归纳法可证：
T(n)≤72c1n
即,T(n) = Ο(n)
SELECT2的实现
算法中需要解决的两个问题
1) 如何确定子集合的中间值当 r较小时，采用 INSERTIONSORT(A,i,j)直接对每组的
r个元素分类，在分类好的序列中，中间元素即为当前 r个元素中的中间位置下标对应的元素。
2) 如何保存 个子集合的中间值注：各组找到的中间元素值将调整到数组 A的前部，连续保存，从而可用递归调用的方式对这些中间值进行排序并找出中间值的中间值。
rn
算法 2.17SELECT2的 SPARKS的描述
procedure SEL(A,m,p,k)
//返回一个 i，使得 i∈[m,p],且 A(i)是 A(m:p)中第 k小元素,r是一个全程变量，其取值为大于
1的整数
global r; integer n,i,j
if p-m+1≤r then call INSERTIONSORT(A,m,p); return (m+k-1); endif
loop
n←p -m+1 //元素数 //
for i←1 to do // 计算中间值 //
call INSERTIONSORT(A,m+(i-1)*r,m+i*r-1) //将中间值收集到 A(m:p)的前部 //
call INTERCHANGE(A(m+i-1),A(m+(i-1)r + -1))
repeat
j←SEL(A,m,m+ -1,)//mm//
call INTERCHANGE (A(m),A(j)) //产生划分元素，将之调整到第一个元素 //
j←p+1
call PARTITION(m,j)
case
:j-m+1=k,return(j)
:j-m+1>k,p←j -1
:else,k←k -(j-m+1);m←j+1
endcase
repeat
end SEL
n/r
n/r/2n/r
r/2
—— ―分”而治之
2.1 一般方法
对大规模问题的求解
利用分治法求解大规模问题
Q q 2
q k
q 1
子 问 题
.,,
a 2
a k
a 1
子 问 题 求 解
.,,
问 题
A
子 结 果合 并分 解逐 步 细 化 的 过 程
1.分治策略基本思想当问题的规模较大而无法直接求解时，将整个问题分成若干个小问题，然后 分而治之 。
可用递归过程描述。
一般情况下，子问题与原始问题,同质”
算法 2.1 分治策略的抽象化控制
procedure DANDC(p,q)
global n.A(1:n);
integer m,p,q; //1≤p≤q≤n //
if SMALL(p,q)
then return(G(p,q))
else
m←DIVIDE(p,q) //p ≤m ＜ q//
return(COMBINE(DANDC(p,m),
DANDC(m+1,q)))
endif
end DANDC
注：
k=2,二分 是最常用的分解策略；
SMALL(p,q),布尔函数，判断输入规模 q-p+1是否足够小而无需再进一步分就可求解；
G(p,q),当 SMALL(p,q)为真时，
对输入规模为 q-p+1的子问题求解；
DIVIDE(p.q),当规模 q-p+1还较大时，对规模为 q-p+1的子问题进一步分解，返回值为 [p,q]区间进一步的 分割点 ；
COMBINE(x,y),子结果的合并函数，将区间 [p,m]和 [m+1,q]上的子问题的解合并成区间 [p,q]上的
“较完整”的解。当 p=1,q=n时，
就得到整个问题的解。
2,分治策略的抽象化控制过程
DANDC的计算时间若所分成的两个子问题的规模大致相等，则 DANDC总的计算时间可用递归关系式表示如下：
g(n) n足够小
T(n) =
2T(n/2) + f(n) 否则注：
T(n),表示输入规模为 n的 DANDC计算时间
g(n),表示对足够小的输入规模直接求解的计算时间
f(n),表示 COMBINE对两个子区间的子结果进行合并的时间
（该公式针对具体问题有各种不同的变形）
2.2 二分检索（折半查找）
1,问题的描述已知一个按 非降次序 排列的元素表 a1,
a2,…,a n，判定某给定的元素 x是否在该表中出现。
若是，则找出 x在表中的位置并返回其所在位置的下标
若非，则返回 0值。
问题的 形式描述,
I=(n,a1,a2,…,a n,x)
问题分解：选取下标 k，由此将 I分解为 3个子问题：
I1=(k-1,a1,a2,…,a k-1,x)
I2=(1,ak,x)
I3=(n-k,ak+1,a2,…,a n,x)
对于 I2，若 ak=x，则有解 k，对 I1,I3不用再求解；否则，
若 x<ak，则只在 I1中求解，对 I3不用求解；
若 x>ak，则只在 I3中求解，对 I1不用求解；
对 I1,I3的求解可 再次 采用分治方法求解
2,二分检索二分检索：每次选取 中间元素 的下标算法 2.3 二分检索
procedure BINSRCH(A,n,x,j)
integer low,high,mid,j,n;
low← 1; high← n;
while low≤high do
mid ←
case
:x<A(mid):high←mid -1
:x>A(mid):low ←mid+1
:else:j←mid;return
endcase
repeat
j←0
end BINSRCH
h i g h ) / 2( l o w?
注,
给定一个按非降次序排列的元素数组 A(1:n),n≥1,
判断 x是否出现。
若是，置 j，使得 x=A(j)
若非,j=0
例 2.1：设 A(1:9)=(-15,-6,0,7,9,23,54,82,101)
在 A中检索 x=101,-14,82。执行轨迹见下表 1
表 1 运行轨迹示例
x=101 x=-14 x=82
low high mid low high mid low high mid
1 9 5 1 9 5 1 9 5
6 9 7 1 4 2 6 9 7
8 9 8 1 1 1 8 9 8
9 9 9 2 1 找不到 找到找到成功 的检索 不成功 的检索 成功 的检索定理 2.1 过程 BINSRCH(A,n,x,j)能正确运行证明：
1）在具体指定 A中的数据元素及 x的数据类型后，算法中的所有运算都能按要求正确运行 ——即首先满足 确定性 和 能行性
2）终止性算法初始部分置 low←1,high←n
① 若 n=0，不进入循环,j置 0，算法终止
② 否则，进入循环，计算 mid,
或 x=A(mid),j置为 mid，算法终止；
或 x<A(mid)，置 high←mid -1，搜索范围实际缩小为 [low,mid-1]，
进入下次循环，对 [mid+1,high]区间不做进一步搜索；
或 x>A(mid)，置 low←mid+1,进入下次循环；搜索范围实际缩小为 [mid+1,high]，对 [low,mid-1]区间不做进一步搜索；
因 low,high,mid都是 整型 变量，故按照上述规则，在 有限步 内，或找到某个 mid，有 A(mid) = x；或变得 low>high，在 A中没有找到任何元素等于 x，算法终止。
3,性能分析
1）空间特性
n+5个空间位置 (A,x,j,mid,low,high)——О(n)
2) 时间特性区分以下情况进行分析
成功检索,指所检索的 x恰好在 A中出现。
由于 A中共有 n个元素，故成功检索恰好有 n种可能的情况
不成功检索,指 x不出现在 A中。
根据取值，不成功检索共有 n+1种可能的情况（ 取值区间 ）：
x<A(1) 或 A(i)<x<A(i+1),1≤i<n -1 或 x>A(n)
成功 /不成功检索的 最好情况,执行步数最少，计算时间 最短
成功 /不成功检索的 最坏情况,执行步数最多，计算时间 最长
成功 /不成功检索的 平均情况,一般情况下计算时间的 平均值实例分析（例 2.1）
运算的频率计数
1,while循环体外语句的频率计数为 1
2,集中考虑 while循环中 x与 A
中元素的 比较 运算
——其它运算的频率计数与比较运算相同的数量级
3,case语句的分析,假定只需 一次 比较就可确定 case
语句控制是三种情况的哪一种。
procedure BINSRCH(A,n,x,j)
integer low,high,mid,j,n;
low← 1; high← n;
while low≤high do
mid ←
case
:x<A(mid):high←mid -1
:x>A(mid):low ←mid+1
:else:j←mid;return
endcase
repeat
j←0
end BINSRCH
h i g h ) / 2( l o w?
实例分析（例 2.1）
查找每个元素所需的元素比较次数统计如下：
A ⑴ ⑵ ⑶ ⑷ ⑸ ⑹ ⑺ ⑻ ⑼
元素 -15 -6 0 7 9 23 54 82 101
成功检索 比较次数 3 2 3 4 1 3 2 3 4
不成功检索 比较次数 3 3 3 4 4 3 3 3 4 4
成功检索最好,1次最坏,4次平均,（ 3+2+3+4+1+3+2+3+4） /9≈ 2.77次
不成功检索最好,3次最坏,4次平均,(3+3+3+4+4+3+3+3+4+4)/10 = 3.4次二元比较树算法执行过程的主体是 x与一系列中间元素 A(mid)比较 。可用一棵二元树描述这一过程，称为 二元比较树
结点,分为 内结点 和 外结点 两种
内结点,· 代表一次 元素比较
· 用 圆形 结点表示
· 存放一个 mid值 (下标 )
· 代表 成功检索 情况
外结点,· 用方形结点表示，
· 表示 不成功检索 情况
路径,代表检索中元素的比较序列 例 2.1的二元比较树
5
2 7
1 3 6
8
4
9
二元比较树的查找过程
若 x在 A中出现，则算法的执行过程在一个圆形的 内结点 处结束
若 x不在 A中出现，则算法的执行过程在一个方形的 外结点 处结束注：外结点不代表元素的比较，因为比较过程在该外结点的 上一级 的内结点处结束。
5
2 7
1 3 6
8
4
9
例 2.1的二元比较树定理 2.2 若 n在区域 [2k-1,2k)中，则对于 一次成功的检索,
BINSRCH至多做 k次比较；对于 一次不成功的检索,
或者做 k-1次比较，或者做 k次比较。
证明要点：
二分检索中，每次 mid取中值，故其二元比较树是一种,结点平衡,的树，
★ 当 2k-1≤n< 2k时,结点分布 情况为：
内结点,1至 k级外结点,k级或 k+1级，
★ 外部结点在相邻的两级上 ——最深一层或倒数第 2层
比较过程：
成功检索在内结点处结束，不成功检索在外结点处结束
成功检索在 i级的某个内结点终止时，所需要的元素比较次数是 i
不成功检索在 i级的外部结点终止所需的元素比较次数是 i-1
BINSRCH的计算复杂度
n∈ [2k-1,2k)
k≈logn
1）外结点在最末的两级上，故不成功检索的最好、
最坏和平均情况的计算时间均为
2）最好情况下，成功检索的计算时间为最坏情况下，成功检索的计算时间为
Θ (lo gn )
Θ(1)
Θ (lo gn )
3）平均情况下的成功检索的计算时间利用 外部结点和内部结点到根距离和之间的关系 进行推导。
记，
由根到所有内结点的距离之和称为 内部路径长度,记为 I；
由根到所有外部结点的距离之和称为 外部路径长度,记为 E。
则有,E=I+2n · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ①
记，
U(n)是平均情况下不成功检索的计算时间，则
U(n) = E/(n+1) · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ②
S(n)是平均情况下成功检索的计算时间，则
S(n) = I/n + 1 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ③
由 ① ② ③得,
S(n) = (1+1/n)U(n) -1
当 n→∞,S(n) ∝ U(n),而 U(n) =
所以 S(n) =
Θ (lo gn )
Θ (lo gn )
成功检索最好 平均 最坏
Θ(1) Θ(logn) Θ(logn)
不成功检索最好 平均 最坏
Θ(logn) Θ(logn)Θ(logn)
4,以比较为基础检索的时间下界问题,设 n个元素的有序表 A(1:n),A(1)< A(2) < …< A(n) 。检索一给定元素 x是否在 A中出现。
问：是否预计还存在有以 元素比较 为基础的另外的检索算法，它在最坏情况下比二分检索算法在计算时间上有 更低 的数量级?
以比较为基础的算法,假定算法中只允许进行元素间的 比较,而不允许对它们实施其它运算。
内结点,表示一次元素的比较，并代表 成功检索 情况。每棵比较树中恰好含有 n个内结点，分别与 n个不同 i值相对应；
外结点,代表不成功检索情况。每棵比较树中恰好有 n+1个外结点分别与 n+1中不成功检索情况相对应。
分析：任何以比较为基础的检索算法，其执行过程都可以用二元比较树 来描述。
以比较为基础 的 有序检索 问题最坏情况的 时间下界定理 2.3 设 A(1:n)含有 n(n≥1) 个不同的元素，且有
A(1) < A(2) < …< A(n)
又设，用以比较为基础的算法去判断给定的 x是否有则，最坏情况下，任何这样的算法所需的最小比较次数 FIND(n)
有：
n):A ( 1x?
1)l o g ( nF I N D ( n )
证明：
① 从模拟求解检索问题算法的比较树可知,FIND(n)不大于 树中由根到一个叶子的最长路经的距离。
② 在所有的二元比较树中必定有 n个内结点分别与 x在 A中的 n中可能的出现相对应。
③ 如果一棵二元树的所有内结点所在的级数小于或等于 k，则该树中最多有 2k-1个内结点。
故,n≤2 k-1,即
1)l o g ( nkF I N D ( n )
结论
1）任何一种以比较为基础的有序检索算法，在 最坏情况 下的计算时间都 不低于 Ο(logn)。因此,不可能存在最坏情况比二分检索数量级还低的算法。
2）二分检索是解决检索问题的 最优 的 最坏情况 算法
2.3 找最大和最小元素查找问题：
1) 在元素表中确定某给定的元素的位置或判定其不出现：二分检索，顺序查找
2) 在元素表单独或同时找出其中的最大和
（或）最小
3) 在元素表找出其中第一小（大）和第二小
（大）元素
4) 找元素表中的第 k小元素：排序或选择等等本节问题：在元素表同时找出最大元素和最小元素问题描述,给定含有 n个元素的集合（以数组 A表示），找出其中的最大和最小元素。
二种算法的比较：
迭代算法递归算法
1,直接找最大和最小元素算法 2.5 直接找最大和最小元素
procedure STRAITMAXMIN(A,n,max,min)
//将 A中的最大值置于 max，最小值置于 min//
Integer i,n
max←min←A(1)
for i←2 to n do
if A(i) > max then
max←A(i)
endif
if A(i) < min then
min←A(i)
endif
repeat
end STRAITMAXMIN
算法的性能：
只考虑算法中的 比较运算,以此代表算法的执行特征；
该算法最好、最坏、
平均情况下均需要做
2（ n-1） 次元素比较
STRAITMAXMIN算法的一种简单改进形式,
procedure STRAITMAXMIN1(A,n,max,min)
integer i,n
max←min←A(1)
for i←2 to n do
if A(i) > max then max←A(i) endif
else if A(i) < min then min←A(i) endif
repeat
end STRAITMAXMIN1
这使得，
最好情况,按 递增次序 排列，元素比较次数为 n-1次
最坏情况,按 递减次序 排列，元素比较次数为 2(n-1)次
平均情况,元素比较次数为 3(n-1)/2次
2,分治求解策略记问题的一个实例为：
I = (n,A(1),…,A(n))
采用二（等）分法将 I分成两个子集合处理
I1 = (,A(1),…,A( ))，和
I2 = (n-,A( +1),…,A(n))
则有，
MAX(I) = max(MAX(I1),MAX(I2))
MIN(I) = min(MIN(I1),MIN(I2))
MAX(I)和 MIN(I)分别代表 I中元素的最大者和最小者采用 递归 的设计策略，得到以下算法：
n/2n/2
n/2n/2
3,找最大最小元素的递归求解算法算法 2.6 递归求取最大和最小元素
procedure MAXMIN(i,j,fmax,fmin)
//A(1:n)是含有 n个元素的全局数组，参数 i,j是整数,1≤i,j≤n,代表当前的查找区间 //
//该过程把 A(i:j)中的最大和最小元素分别赋给 fmax和 fmin //
integer i,j;global n,A(1:n)
case
:i=j,fmax←fmin←A(i) // 只有一个元素
:i=j-1:if A(i)<A(j) then fmax←A(j);fmin←A(i)
else fmax←A(i);fmin←A(j) // 两个元素的情况
endif
:else,mid← // 取中，并在两个子区间上作递归调用
call MAXMIN(i,mid,gmax,gmin)
call MAXMIN(mid +1,j,hmax,hmin)
fmax←max(gmax,hmax); fmin←min(gmin,hmin)
end case
end MAXMIN
j)/2(i?
MAXMIN过程的初始调用,
MAXMIN（ 1,n,fmax,fmin）
数组 A是全局数组
fmax,fmin带出 A(1:n)中的最大和最小元素例：在 A(1:9) = (22,13,-5,-8,15,60,17,31,47)上执行算法 2.6
每个结点内的值分别是：
i,j,fmax,fmin
递归调用递归调用分解过程递归调用的返回区间划分将一直进行到只含有 1个或 2个元素时为止，然后求子解，并返回
MAXMIN过程的性能分析 ——仅考虑算法中的 比较运算
0 n=1
T(n) = 1 n=2
n>2
当 n是 2的幂时 (n=2k),化简上式有，
T(n)=2T(n/2) +2
=2(2T(n/4) + 2) + 2
…
=2k-1T(2) +
=2k-1+2k-2
=3n/2-2
2)n / 2T()n / 2T(
1ki1 i2
性能比较
1）与 STRAITMAXMIN算法相比，比较次数减少了 25%
（ 3n/2-2,2n-2)。
已经达到了以 元素比较为基础 的找最大最小元素的算法计算时间的 下界,
2）存在的问题 ——递归调用造成：
空间占用量大有 级的递归，入栈参数：
i,j,fmax,fmin和返回地址五个值。
时间可能不比预计的理想如果元素 A(i)和 A(j)的比较与 i和 j的比较在 时间 上 相差不大 时，算法 MAXMIN不可取 。
22/3?n
1lo g?n
假设元素的比较与 i和 j的比较时间相同（整型数）。又设对 case语句调整，使得仅需一次 i和 j的比较就能够确定是哪种情况。
case
:i>=j-1:if A(i)<A(j) then fmax←A(j);fmin←A(i)
else fmax←A(i);fmin←A(j) // 两个元素的情况
endif
:else,?
记此时 MAXMIN的频率计数为 C(n),n=2k (k为正整数）。则有，
2 n<=2 (一次是 i和 j-1的比较，一次是 A(i)和 A(j)的比较 )
C(n) =
2C(n/2)+3 n>2
化简得，
C(n) = 2C(n/2) + 3
= …
= 5n/2 -3
按照同样的假设，重新估算 STRAITMAXMIN算法的比较次数为,3(n-1)。
STRAITMAXMIN与 MAXMIN在计算时间上的差异越来越小
1/4 （ 25%） =>1/6（ 16.7%）
考虑 MAXMIN算法 递归调用的开销,此时 MAXMIN算法的效率可能还不如 STRAITMAXMIＮ算法。
结论：如果 A中的元素间的比较代价远比整型数
（下标）的比较 昂贵,则分治方法将产生一个 效率较高 的算法；
反之，可能仅得到一个 低效 的算法。
故，分治策略只能看成一个 较好的 但 并不总是成功的算法设计指导。
2.4 归并分类
1,分类问题 ——排序给定一 n个元素的集合 A，按照某种方法将 A中的元素按非降或非增次序排列。
分类：内排序，外排序常见内排序方法：冒泡排序插入排序归并排序快速排序堆排序
…
2,插入分类算法 2.7 插入分类
procedure INSERTIONSORT(A,n)
//将 A(1,n)中的元素按非降次序分类,n≥1//
A(0)← -∞//设置初始边界值
for j←2 to n do //A(1:j -1)已分类 //
item←A(j);i←j -1
while item<A(i) do //0≤i<j//
A(i+1)←A(i); i←i -1
repeat
A(i+1) ←item;
repeat
end INSERTIONSORT
i指示的是 j之前的一位，即当前已排序子表的最末一个元素的下标性能分析：
最坏 情况：输入数据按非增次序排列,每次 内层
while循环 执行 j次（ j=2,3,…,n) 。则有，
最好 情况：输入数据已按非降序排列，不进入
while循环，则最好情况下计算时间为 Ω(n)
)Θ ( n 2?
1 1 ) ) / 2( n ( nj
nj2
3.分治策略求解基本设计思想：将原始数组 A中的元素分成两个子集合,A1(1,)和 A2( +1,n)。分别对这两个子集合单独分类，然后将已分类的两个子序列 归并 成一个含有 n个元素的分类好的序列。
这样的一个分类过程称为 归并分类 。
n/2n/2
算法 2.8 归并分类
procedure MERGESORT(low,high)
//A(low:high)是一个全程数组,low和 high分别指示当前待分类区间的最小下标和最大下标，含有 high-low+1≥0 个待分类的元素 //
integer low,high
if low<high then //当含有 2个及 2个以上的元素时，作划分与递归处理 //
mid← //计算 中分点 //
call MERGESORT(low,mid) //在第一个子集合上分类 (递归 )//
call MERGESORT(mid+1,high) //在第二个子集合上分类 (递归 )//
call MERGE(low,mid,high) //归并已分类的两子集合 //
endif
end MERGESORT
h i g h ) / 2( l o w?
算法 2.9 使用辅助数组归并两个已分类的集合
procedure MERGE(low,mid,high)
//A(low,high)是一个全程数组,它含有两个放在 A(low,mid)和 A(mid+1,high)中的已分类的子集合,目标是将这两个已分类的集合归并成一个集合，并存放到 A(low,high)中 //
integer h,I,j,k,low,mid,high;//low≤mid＜ high//
global A(low,high);local B(low,high)
h←low;i←low; j←mid+1;
while h≤mid and j≤high do //当两个集合都没有取尽时,将较小的元素先存放到 B中 //
if A(h)≤A(j) then B(i) ←A(h);h←h+1 //如果前一个数组中的元素较小 //
else B(i) ←A(j); j←j+1 //如果后一个数组中的元素较小 //
endif
i← i+1
repeat
//处理尚有剩余元素的集合 //
if h>mid then for k←j to high do B(i) ←A(k);i←i+1; repeat
else for k←h to mid do B(i) ←A(k);i←i+1; repeat
endif
for k ←low to high do A(k) ←B(k) repeat //将已归并的集合复制到 A中 //
end MERGE
性能分析
1) 过程 MERGE的归并时间与两数组元素的总数成正比故可表示为,cn,n为元素数,c为某正常数
2) 过程 MERGESORT的分类时间用递推关系式表示如下,
a n=1,a是常数
T(n)=
2T(n/2)+cn n>1,c是常数化简,若 n=2k,则有,
T(n) =2(2T(n/4)+cn/2)+cn
= 4T(n/4) + 2cn =4T(2T(n/8) +cn/4) + 2cn
= …
=2kT(1)+kcn
=an+cnlogn //k=logn//
若 2k<n<2k+1,则有 T(n)≤T(2k+1)。
所以得,T(n) = Ο(nlogn)
递归调用一直进行到子区间仅含一个元素时为止归并分类示例
设 A=（ 310,285,179,652,351,423,861,254,450,520）
1）划分过程
310,285,179,652,351,423,861,254,450,520
310,285,179,652,351 423,861,254,450,520
310,285,179 652,351
310,285 179
310 285
652 351
423,861,254 450,520
423,861 254
423 861
450 520
2）归并过程首先进入左分枝的划分与归并。
第一次归并前的划分状态是：
（ 310 | 285 | 179 | 652,351 | 423,861,254,450,520）
第一次归并：（ 285,310 | 179 | 652,351 | 423,861,254,450,520）
第二次归并：（ 179,285,310 | 652,351 | 423,861,254,450,520）
第三次归并：（ 179,285,310 |351,652 | 423,861,254,450,520）
第四次归并：（ 179,285,310,351,652 | 423,861,254,450,520）
进入右分枝的划分与归并过程
（略）
3）用树结构描述归并分类过程
4,归并分类算法的改进
1）算法 2.8存在的问题
递归层次太深在 MERGESORT的执行过程中，当集合仅含有两个元素时，仍要进一步做递归调用，直至每个集合仅含有一个元素时才退出递归调用。
在集合含有仅相当少的元素时，较深层次的递归调用使得时间 过多地消耗 在处理递归上。
元素在数组 A和辅助数组 B之间的频繁移动每次归并，都要首先将 A中的元素移到 B中，在由 B复制到 A的对应位置上。
2）改进措施
针对递归层次问题采用能 在小规模集合 上有效工作的其它算法，直接对小规模集合处理。
如 INSERTIONSORT算法
针对元素频繁移动问题采用一个称为 链接信息数组 LINK（ 1,n） 的数据结构，
记录归并过程中 A中的元素相对于其排序后在分类表中 位置坐标的链接关系。
LINK(i)取值于 [1,n]，是指向 A的元素的指针：在分类表中它指向下一个元素在 A中的位置坐标。
例：
LINK (1) (2) (3) (4) (5) (6) (7) (8)
6 4 7 1 3 0 8 0
该表中含有 两个子表,0表示表的结束。
设置 表头指针 Q和 R分别指向两个子表的起始处：
Q=2,R=5；
则有，
表 1,Q(2,4,1,6),经过分类后有,A(2)≤ A(4) ≤ A(1) ≤ A(6)
表 2,R(5,3,7,8),同样有,A(5)≤ A(3) ≤ A(7) ≤ A(8)
链接信息表在归并过程中的应用,
将归并过程中元素在 A和 B之间移动的过程变成更改 LINK
所指示的链接关系，从而避免移动元素的本身。
分类表可以通过 LINK的表头指针和读取 LINK中的链接关系取得。
改进后的归并分类模型算法 2.10 使用链接信息数组的归并分类模型
procedure MERGESORT1(low,high,p)
//利用链接信息数组 LINK(1:n)将全程数组 A(low:high)按非降次序分类。 LINK中值表示按分类次序给出
A下标的表，并把 p置于该表的开始处 //
global A(low:high),LINK(low,high)
if high-low+1<16 //当集合中的元素个数足够少 (<16)时，采用更有效的小规模集合上的分类算法直接分类 //
then call INSERTSORT1(A,LINK,low,high,p) //算法 2.7的改型 //
else mid←
call MERGESORT1(low,mid,q) //返回 q表 //
call MERGESORT1(mid+1,high,r) //返回 r表 //
call MERGE1(q,r,p) //将表 q和表 r归并成表 p//
endif
end MERGESORT1
h i g h ) / 2( l o w?
算法 2.11 使用链接表归并已分类的集合
procedure MERGE1(q,r,p)
//q和 r是全程数组 LINK(1:n)中两个表的指针。归并这两个表，得到一个由 p所指示的新表。此表将
A中的元素按非降次序分类。 LINK(0)被定义 //
global n,A(1:n),LINK(1:n)
local integer i,j,k
i←q;j←r;k←0 //新表在 LINK(0)处开始 //
while i≠0 and j≠0 do //当两表均非空时 //
if A(i) ≤ A(j) //找较小的关键字 //
then LINK(k) ←i;k←i;i←LINK(i) //加一个新关键字到表中 //
else LINK(k) ←j;k←j;j←LINK(j) //加一个新关键字到表中 //
endif
repeat
if i=9 then LINK(k) = j
else LINK(k) = i
endif
end MERGE1
MERGESORT1 的调用
在初次调用时，待分类的 n个元素放于 A(1:n)中。
LINK(1:n)初始化为 0；
初次调用,call MERGESORT1(1,n,p)
p作为按分类次序给出 A中元素的指示表的指针。
3）改进归并分类算法示例设元素表：（ 50,10,25,30,15,70,35,55）
采用 MERGESORT1对上述元素表分类（不做小规模集合的单独处理）
下表给出在每一次调用 MERGESORT1结束后,LINK数组的变化情况。
在上表的最后一行,p=2返回，得到链表（ 2,5,3,4,7,1,8,6）
即,A(2)≤ A(5)≤ A(3)≤ A(4)≤ A(7)≤ A(1)≤ A(8)≤ A(6)
5,以比较为基础分类的时间下界
1.分类的“实质”
给定 n个记录 R1,R2,…,R n,其相应的关键字是 k1,k2,…,k n。
分类就是确定 1,2,…,n 的一种排列 P1,P2,…P n,使得记录的关键字满足以下非递减（或非递增）排列关系
kP1≤ kP2≤ … ≤ kPn
从而使 n个记录成为一个按关键字有序的序列：
{ RP1,RP2,…,R Pn }
2,以关键字比较为基础的分类算法的时间下界最坏情况下的时间下界为,Ω(nlogn)
利用 二元比较树 证明。
假设参加分类的 n个关键字 A(1),A(2),?,A(n) 互异。任意两个关键字的比较必导致 A(i)<A(j)或 A(i)>A(j)的结果。
以二元比较树描述元素间的比较过程：
若 A(i)<A(j)，进入下一级的 左分支
若 A(i)>A(j)，进入下一级的 右分支算法在 外部结点 终止。
从根到某外结点的 路径 代表某个特定输入情况下一种唯一的 分类排序序列 。 路径长度 表示生成该序列代表的分类表所需要的 比较次数。 而 最长的路径 代表算法在最坏情况下的执行情况，该路径的长度即是算法在最坏情况下所作的比较次数。
故，以比较为基础的分类算法的 最坏情况下界 等于该算法对应的比较树的 最小高度 。
初始集合中的元素因顺序不同，将导致排序过程走不同的分支
① 由于 n个关键字有 n!种可能的排列，所以分类二元比较树中将有
n!个 外部结点,每个外部结点代表一种特定的排列，该排列对应于某种特定输入情况下的分类序列。
② 设一棵二元比较树的所有 内结点 的级数均小于或等于 k，则该树中最多有 2k个外结点。
记算法在最坏情况下所作的比较次数为 T(n),则有 T(n)=k：生成外结点所代表的分类序列所需的比较次数等于该外结点所在的级数 -1；
根据①和②的分析，有：
n!≤2 T(n)
化简：
当 n>1时，有 n!≥n(n -1)(n-2)?( )≥(n/2) n/2
当 n≥4 时，有 T(n)≥(n/2)log(n/2)≥(n/4)logn
故，任何以比较为基础的分类算法的最坏情况的时间下界为：
Ω(nlogn)
n/2
1.划分与快速分类
快速分类是一种基于 划分 的分类方法；
划分,选取待分类集合 A中的某个元素 t，按照与 t的大小关系重新整理 A中元素，使得整理后 t被置于序列的某位置上，
而序列中所有在 t以前出现的元素均 小于等于 t，而所有出现在 t以后的元素均 大于等于 t。这一元素的整理过程称为划分 （ Partitioning）。
元素 t称为 划分元素 。
快速分类,通过 反复 地对待排序集合进行 划分 达到分类目的的分类算法。
2.5 快速分类划分过程（ PARTITION）的算法描述算法 2.2 用 A(m)划分集合 A(m:p-1)
procedure PARTITION(m,p)
integer m,p,i; global A(m:p-1)
v←A(m);i←m //A(m) 是划分元素 //
loop
loop i←i+1 until A(i)≥v repeat // i 由左向右移 //
loop p←p -1 until A(p)≤v repeat //p由右向左移 //
if i<p then
call INTERCHANGE(A(i),A(p))
else exit
endif
repeat
A(m)←A(p) ； A(p)←v // 划分元素在位置 p//
end PARTITION
A(p)被定义，但为一限界值，
不包含在实际的分类区间内。
pi
v v
注：
算法对集合 A(m:p-1)进行划分。并使用待划分区间的第一个元素 A(m)作为划分元素
A(p)不在划分区间内，但被定义，且 A(p） ≥ A(m)，用于限界例 2.5 划分实例
(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) i p
A,65 70 75 80 85 60 55 50 45 +∞ 2 9
|……………………………………|
A,65 45 75 80 85 60 55 50 70 +∞ 3 8
|…………………………|
A,65 45 50 80 85 60 55 75 70 +∞ 4 7
|………………|
A,65 45 50 55 85 60 80 75 70 +∞ 5 6
|……|
A,65 45 50 55 60 85 80 75 70 +∞ 6 5
|……………………|
A,60 45 50 55 65 85 80 75 70 +∞
划分元素定位于此交换划分元素经过一次,划分” 后，实现了对集合元素的调整：
以划分元素为界，左边子集合的所有元素均 小于等于 右边子集合的所有元素。
按同样的策略对两个子集合进行分类处理。当子集合分类完毕后，整个集合的分类也完成了。这一过程避免了子集合的归并操作。这一分类方法称为快速分类 。
2.快速分类算法
——一种通过反复使用划分过程 PARTITION实现对集合元素分类的算法。
算法 2.13 快速分类
procedure QUICKSORT(p,q)
//将数组 A(1:n)中的元素 A(p),…A(q) 按递增的方式分类。
A(n+1)有定义,且假定 A(n+1)←+ ∞//
integer p,q;global n,A(1:n)
if p<q then
j←q+1 //进入时,A(j)定义了划分区间 [p,q]的 上界,首次调用时 j=n+1
call PARTITION(p,j) //出口时,j带出此次划分后划分元素所在的 下标位置 //
call QUICKSORT(p,j-1) //对前一子集合递归调用
call QUICKSORT(j+1,q) //对后一子集合递归调用
endif
end QUICKSORT
3,快速分类分析
统计的对象：元素的 比较次数,记为,C(n)
两点假设
① 参加分类的 n个元素各不相同
② PARTITION中的划分元素 v是 随机 选取的（针对平均情况的分析）
随机选取划分元素,
在划分区间 [m,p-1]随机生成某一坐标,i←RANDOM(m.p -1)；
调换 A(m)与 A(i):v←A(i);A(i) ←A(m);i←m
作用：将随机指定的划分元素的值调换到 A(m)位置。算法主体不变。之后，仍从 A(m)开始执行划分操作。
递归层次
QuickSort(1,n)
QuickSort(1,j1-1) QuickSort(j1-1,n)
QuickSort(1,j21-1) QuickSort(j21+1,j1-1) QuickSort(j1-1,j22-1) QuickSort(j22+1,n)
n个元素参加划分和分类去掉 1个第一级的划分元素
n-1个元素参加划分和分类去掉 2个第二级的划分元素
n-3个元素参加划分和分类去掉 4个第三级的划分元素第一层第二层第三层设在任一级递归调用上，调用 PARTITION处理的所有元素总数为 r，则，初始时 r=n，以后的每级递归上，由于删去了上一级的划分元素，故 r比上一级至少 1：
理想情况,第一级少 1，第二级少 2，第三级少 4,… ；
最坏情况,每次仅减少 1（每次选取的划分元素刚好是当前集合中最小或最大者）
最坏情况分析
记 最坏情况 下的元素比较次数是 Cw(n)；
PARTITION一次调用中的元素比较数是 p-m+1,故每级递归调用上,PARTITION所做的比较总数为 O(r),r是任一级递归调用上 PARTITION所处理的元素总数。
最坏情况下（元素已有序），每级递归调用的元素总数仅比上一级少 1，故 Cw(n)是 r由 n到 2的累加和。
即,Cw(n)= = Ο(n2)?
nr
r
1
平均情况分析平均情况 是指集合中的元素以任意顺序排列，且任选元素作为划分元素进行划分和分类，在这些所有可能的情况下，算法执行性能的 平均值 。
设调用 PARTITION(m,p)时，所选取划分元素 v恰好是
A(m:p-1)中的第 i小元素（ 1≤i≤p -m）的概率相等。则经过一次划分，所留下的待分类的两个子文件恰好是 A(m:j-1)和
A(j+1:p-1)的概率是,1/(p-m),m≤j<p 。 记 平均情况 下的元素比较次数是 CA(n)； 则有，
其中，
n+1是 PARTITION第一次调用时所需的元素比较次数。
CA(0) = CA(1) = 0
nk AAnA knCkCnnC 11 ))()1((1)(
化简上式可得：
CA(n)/(n+1) = CA(n-1)/n + 2/(n+1)
= CA(n-2)/(n-1) + 2/n + 2/(n+1)
= CA(n-3)/(n-2)+2/(n-1)+2/n+2/(n+1)
= CA(1)/2+
由于所以得,CA(n)<2(n+1)loge(n+1) = Ο(nlogn)
13
/12
nk
k
)1(l o g/1 12
13
nk en xdx
nk
空间分析最坏情况下，递归的最大深度为 n-1.
需要栈空间,O(n)
使用一个迭代模型可以将栈空间总量减至 O(logn)
4,快速分类算法的迭代模型处理策略,每次在 Partition将文件 A(p:q)分成两个文件
A(p:j-1)和 A(j+1,q)后，先对其中 较小 的子文件进行分类。当小的子文件分类完成后，再对较大的子文件进行分类。
栈,需要一个栈空间保存目前 暂不分类 的较大子文件。并在较小子文件分类完成后，从栈中退出最新的较大子文件进行下一步分类。
栈空间需要量,O(logn)
算法的终止,当栈空时，整个分类过程结束。
算法 2.14 QuickSort2(p,q)
integer STACK(1:max),top //max=2
global A(1:n);local integer j
top←0
loop
while p<q do
j←q+1
call PARTITION(p,j);
if j – p < q – j //先对较小的子文件分类，并将规模较大的子文件入栈
then STACK(top+1)←j+1; STACK(top+2)←q; q←j -1
else STACK(top+1)←p; STACK(top+2)←j -1; p←j+1
endif
top←top+2 // 调整栈顶指针
repeat
if top=0 then return endif //如果栈为空，算法结束
q←STACK(top);p←STACK(top -1); top←top -2 //从栈中退出先前保存的较大的子文件
repeat
end QUICKSORT2
nlog
快速分类算法迭代模型的空间分析算法 2.14的最大空间是 O(logn)
推导：
设算法所需的最大栈空间是 S(n)，则有
1n 0
1n )2/)1((2)( nSnS
2.6 选择问题
1,问题描述在 n个元素的表 A(1:n)中确定第 k小元素,1≤k≤n 。
2,设计思路利用 PARTITION过程。在第一次划分后划分元素 v测定在 A(j)的位置上，则有 j-1个元素小于或等于 A(j)，且有 n-j个元素大于或等于 A(j)。此时，
若 k=j，则 A(j)即是第 k小元素；否则，
若 k<j，则 A(1:n)中的第 k小元素将出现在 A(1:j-1)中,
且仍是 A(1:j-1)中的第 k小元素；
若 k>j，则 A(1:n)中的第 k小元素将出现在 A(j+1:n)中，
但是 A(j+1:n)中的第 k-j小元素。
3,利用 PARTITION实现的选择算法
算法描述算法 2.15 找第 k小元素
procedure SELECT(A,n,k) //在数组 A(1:n)中找第 k小元素，并将之放在 A(k)中。 //
integer n,k,m,r,j;
m←1;r ← n+1;A(n+1) ←+∞ //A(n+1)被定义，并置为一大值，用于限界 //
loop //在进入循环时,1≤m≤k≤r≤n+1 //
j ←r //将剩余元素的最大下标加 1后置给 j //
call PARTITION(m.j) //返回 j,它使得 A(j)是第 j小的值 //
case
:k=j,return
:k<j,r←j //j是新的上界 //
:else,m←j+1 //k>j,j+1是新的下界 //
endcase
repeat
end SELECT
算法分析两点假设
① A中的元素 互异
② 随机选取 划分元素，且选择 A中任一元素作为划分元素的 概率相同分析
每次调用 PARTITION（ m,j),所需的元素比较次数是
Ο(j-m+1)。
在执行一次 PARTITION后，或者找到第 k小元素，或者将在缩小的子集 (A(m,k-1)或 A(k+1,j))中继续查找。缩小的子集的元素数将 至少 比上一次划分的元素数 少 1。
1) 最坏情况
SELECT的最坏情况时间是 Ο(n2)
最坏情况下的特例：
输入 A恰好使对 PARTITION的第 i次调用选用的划分元素是第 i小元素，
而 k=n。
此时，（区间下界） m随着 PARTITION的每一次调用而仅增加 1,j
保持不变。 PARTITION最终需要调用 n次。
则,n次调用的时间总量是
)())1(( 2
1
ni
n
2) 平均情况设 是找 A(1:n)中第 k小元素的平均时间。 是
SELECT的平均计算时间，则有并定义则有,T(n)≤R(n)。
nk
k
AnA nTnT
1
1 )()(
)(nTA
)}({m a x)( nTnR kAk?
)(nTkA
对 n个不同的元素，问题实例可能的 n!种不同情况，综合考查所得的平均值在所有可能的情况下，找所有可能的 k小元素某个特定的 k
定理 2.4 SELECT的平均计算时间 TA(n)是 Ο(n)
证明：
PARTITION的一次执行时间是 Ο(n)。 在随机等概率选择划分元素时，首次调用 PARTITION中划分元素 v刚好是 A中第 i
小元素的概率为 1/n,1≤ i≤ n。
则，存在正常数 c,c>0,有，
n≥2
且有，
n≥2
1 ) )(iTi)(nT(cn( n )T
nik
k
A
ki1
ik
An1
k
A
1 ) }(iRi)(nR{m a xcnR ( n )
nikki1kn
1
( i ) }R( i )R{m a xcn
1n
k
1n
1knk
n
1
划分元素 i<k,将在 i的后半部分求解划分元素 i>k,将在 i
的前半部分求解令 c≥R(1) 。利用 数学归纳法 证明，对所有 n≥2,有 R(n)≤4cn.
① 当 n=2时，由上式得：
② 假设对所有的 n,2≤n<m，有 R(n)≤4cn
③ 当 n = m时，有，
由于 R(n)是 n的非降函数，故当 m为偶数而 k=m/2，或当 m为奇数而
k=(m+1)/2时,取得极大值。因此，
若 m为偶数,则若 m为奇数,则由于 TA(n)≤R(n)，所以 TA(n)≤4cn。 故,TA(n)=Ο(n)
R ( 1 ) }m a x { R ( 1 ),212cR ( n )
4cn2.5c
( i) }R( i)R{m a xcm)( 1m
k
1m
1kmk
m1
nR
1m
m / 2
m2 R ( i)cmR ( m )?
1m
m / 2
m
8c 4 c micm
1m
1 ) / 2(m
m
2 R ( i )cmR ( m )?
1m
1 ) / 2(m
m
8c 4 c micm
( i)R( i)R 1n
k
1n
1kn
1 k m-1
1 m– k+1 m-1
4,最坏情况是 Ο(n)的选择算法
1）采用两次取中间值的规则精心选取划分元素首先，将参加划分的 n个元素分成 组，每组有 r个元素 (r≥1) 。（多余的 个元素忽略不计）
然后，对这 组每组的 r个元素进行分类并找出其中间元素 mi,1≤i≤,共得 个中间值。
之后，对这 个中间值分类，并找出其中间值 mm。
将 mm作为划分元素执行划分。
2）算法描述
n/r
n/rrn?
n/r
n/rn/r
n/r
例：设 n=35,r=7。
分为 n/r = 5个元素组：
B1,B2,B3,B4,B5；
每组有 7个元素。
B1-B5按照各组的 mi的非增次序排列。
mm = mi的中间值,1≤i≤5
由图所示有,
mm
中间值小于等于 mm的元素大于等于 mm的元素非降次序
B1 B2 B3 B4 B5
按照 mi的非降次序排列由于 r个元素的 中间值 是第 小元素。则，
至少有 个 mi小于或等于 mm；
至少有 个 mi大于或等于 mm。
故，至少有 个元素小于或等于（或大于或等于） mm。
当 r=5，则使用两次取中间值规则来选择 v=mm，可得到，
至少有 个元素小于或等于选择元素 v。
且至多有 个元素大于 v。
同理，至多有 0.7n+1.2个元素小于 v。
故，这样的 v可 较好 地划分 A中的 n个元素。
/2n / r1/2n / rn / r
2/n/r
2/r
/2n /rr/2
n/55.1
1,20,7 nn / 51,5n
算法 2.16 使用二次取中规则的选择算法的说明性描述
Procedure SELECT2(A,k,n)
//在集合 A中找第 k小元素
① 若 n≤r，则采用插入法直接对 A分类并返回第 k小元素
② 把 A分成大小为 r的 个子集合，忽略多余的元素
③ 设 M={m1,m2,…m } 是 子集合的中间值集合
④ v← SELECT2(M,,)
⑤ j← PARTITION(A,v)
⑥ case
:k=j,return(v)
:k<j,设 S是 A(1:j-1)中元素的集合 ; return(SELECT2(S,k,j-1))
:else,设 R是 A(j+1:n)中元素的集合 ; return(SELECT2(R,k-j,n-j))
endcase
end SELECT2
n/r
n/r
n/r2/n/r
n/r
2) 算法分析记 T(n)是 SELECT2所需的最坏情况时间对特定的 r分析 SELECT2:选取 r=5。
假定 A中的元素各不相同，则有
① 若 n≤r，则采用插入法直接对 A分类并返回第 k小元素 → Ο(1)
② 把 A分成大小为 r的 个子集合，忽略多余的元素 → Ο(n)
③ 设 M={m1,m2,…m r }是 子集合的中间值集合 → Ο(n)
④ v← SELECT2(M,,) → T(n/5)
⑤ j← PARTITION(A,v) → Ο(n)
⑥ case →T(3n/4),n ≥24
:k=j,return(v)
:k<j,设 S是 A(1:j-1)中元素的集合 ; return(SELECT2(S,k,j-1))
:else,设 R是 A(j+1:n)中元素的集合 ; return(SELECT2(R,k-j,n-j))
endcase
end SELECT2
n/r
n/r
n/r2/n/r
r为定值，记对 r个元素的直接排序的时间为“定值”
故有，
cn n ＜ 24,
T(n)＝
T(n/5)+T(3n/4)+cn n≥24
用归纳法可证：
T(n)≤20cn
故，在 r=5地情况下，求解 n个不同元素选择问题的算法
SELECT2的最坏情况时间是 Ο(n)。
当 A中的元素 不尽相同步骤⑤经 PARTITION调用所产生的 S和 R两个子集合中可能存在一些元素 等于 划分元素 v,可能导致 |S|或 |R|大于 0.7n+1.2。
改进：
方法一：将 A集合分成 3个子集合 U,S和 R，其中 U是由 A中所有与 v相同的元素组成,S是由 A中所有比 v小的元素组成,R则是 A中所有比 v大的元素组成。
同时步骤⑥更改：
case
:|S|≥k:return(SELECT2(S,k,|S|)
:|S|+|U|≥k:return(v)
:else,return(SELECT2(R,k-|S|-|U|,|R|))
endcase
从而保证 |S|+|R|≤0.7n+1.2 成立，故关于 T(n)的分析仍然成立。
T(n) = Ο(n)
方法二：选取其他的 r值进行计算特例：当 r=5,且 A中的元素不尽相同。假设其中有 0.7n+1.2个元素比 v小而其余的元素都等于 v的情况。
则，经过 PARTITION，在这些等于 v的元素中至多有一半可能在 S中，
故 |S|≤0.7n+1.2+(0.3n -1.2)/2=0.85n+0.6
同理,|R|≤0.85n+0.6
可得，此时步骤④和⑥所处理的元素总数将是
1.05n+0.6>n
不再是 线性 关系。故有 T(n)≠ Ο(n)
改进：
取 r=9。经计算可得，此时将有 个元素小于或等于 v，同时至少有 大于或等于 v。
则 当 n≥90 时,|S|和 |R|都至多为基于上述分析，有新的递推式：
n/92.5
72/6325.136/319/25.1)9/5.2(9/5.2 21 nnnnnnn
相等元素的一半n/92.5
故有，
c1n n＜ 90
T(n) ＝
T(n/9)+T(63n/72)+c1n n≥90
用归纳法可证：
T(n)≤72c1n
即,T(n) = Ο(n)
SELECT2的实现
算法中需要解决的两个问题
1) 如何确定子集合的中间值当 r较小时，采用 INSERTIONSORT(A,i,j)直接对每组的
r个元素分类，在分类好的序列中，中间元素即为当前 r个元素中的中间位置下标对应的元素。
2) 如何保存 个子集合的中间值注：各组找到的中间元素值将调整到数组 A的前部，连续保存，从而可用递归调用的方式对这些中间值进行排序并找出中间值的中间值。
rn
算法 2.17SELECT2的 SPARKS的描述
procedure SEL(A,m,p,k)
//返回一个 i，使得 i∈[m,p],且 A(i)是 A(m:p)中第 k小元素,r是一个全程变量，其取值为大于
1的整数
global r; integer n,i,j
if p-m+1≤r then call INSERTIONSORT(A,m,p); return (m+k-1); endif
loop
n←p -m+1 //元素数 //
for i←1 to do // 计算中间值 //
call INSERTIONSORT(A,m+(i-1)*r,m+i*r-1) //将中间值收集到 A(m:p)的前部 //
call INTERCHANGE(A(m+i-1),A(m+(i-1)r + -1))
repeat
j←SEL(A,m,m+ -1,)//mm//
call INTERCHANGE (A(m),A(j)) //产生划分元素，将之调整到第一个元素 //
j←p+1
call PARTITION(m,j)
case
:j-m+1=k,return(j)
:j-m+1>k,p←j -1
:else,k←k -(j-m+1);m←j+1
endcase
repeat
end SEL
n/r
n/r/2n/r
r/2
