目录
第一章
1.1
1.2
1.3
1.4
第二章
2.1
2.2
第三章
3.1
3.2
3.3
3.4
3.5
Java与面向对象程序设计........................................................................................1
Java语言基础知识....................................................................................................1
1.1.1
基本数据类型及运算.......................................................................................1
1.1.2
流程控制语句...................................................................................................3
1.1.3
字符串...............................................................................................................3
1.1.4
数组...................................................................................................................5
Java的面向对象特性................................................................................................7
1.2.1
类与对象...........................................................................................................7
1.2.2
继承...................................................................................................................9
1.2.3
接口.................................................................................................................10
异常.........................................................................................................................11
Java与指针..............................................................................................................12
数据结构与算法基础.............................................................................................15
数据结构.................................................................................................................15
2.1.1
基本概念.........................................................................................................15
2.1.2
抽象数据类型.................................................................................................17
2.1.3
小结.................................................................................................................19
算法及性能分析.....................................................................................................19
2.2.1
算法.................................................................................................................19
2.2.2
时间复杂性.....................................................................................................20
2.2.3
空间复杂性.....................................................................................................24
2.2.4
算法时间复杂度分析.....................................................................................25
2.2.5
最佳、最坏与平均情况分析.........................................................................27
2.2.6
均摊分析.........................................................................................................29
线性表.....................................................................................................................32
线性表及抽象数据类型.........................................................................................32
3.1.1
线性表定义.....................................................................................................32
3.1.2
线性表的抽象数据类型.................................................................................32
3.1.3
List接口 ..........................................................................................................34
3.1.4
Strategy接口 ...................................................................................................35
线性表的顺序存储与实现.....................................................................................36
线性表的链式存储与实现.....................................................................................42
3.3.1
单链表.............................................................................................................42
3.3.2
双向链表.........................................................................................................46
3.3.3
线性表的单链表实现.....................................................................................48
两种实现的对比.....................................................................................................53
3.4.1
基于时间的比较.............................................................................................53
3.4.2
基于空间的比较.............................................................................................53
链接表.....................................................................................................................54
3.5.1
基于结点的操作.............................................................................................54
3.5.2
链接表接口.....................................................................................................54
3.5.3
基于双向链表实现的链接表.........................................................................56
1
3.6
第四章
4.1
4.2
4.3
第五章
5.1
5.2
5.3
5.4
第六章
6.1
6.2
6.3
6.4
6.5
第七章
迭代器.....................................................................................................................59
栈与队列.................................................................................................................62
栈.............................................................................................................................62
4.1.1
栈的定义及抽象数据类型.............................................................................62
4.1.2
栈的顺序存储实现.........................................................................................63
4.1.3
栈的链式存储实现.........................................................................................65
队列.........................................................................................................................66
4.2.1
队列的定义及抽象数据类型.........................................................................66
4.2.2
队列的顺序存储实现.....................................................................................68
4.2.3
队列的链式存储实现.....................................................................................71
堆栈的应用.............................................................................................................72
4.3.1
进制转换.........................................................................................................72
4.3.2
括号匹配检测.................................................................................................73
4.3.3
迷宫求解.........................................................................................................74
递归.........................................................................................................................78
递归与堆栈.............................................................................................................78
5.1.1
递归的概念.....................................................................................................78
5.1.2
递归的实现与堆栈.........................................................................................80
基于归纳的递归.....................................................................................................81
递推关系求解.........................................................................................................83
5.3.1
求解递推关系的常用方法.............................................................................83
5.3.2
线性齐次递推式的求解.................................................................................85
5.3.3
非齐次递推关系的解.....................................................................................86
5.3.4
Master Method ................................................................................................87
分治法.....................................................................................................................89
5.4.1
分治法的基本思想.........................................................................................89
5.4.2
矩阵乘法.........................................................................................................91
5.4.3
选择问题.........................................................................................................93
树.............................................................................................................................96
树的定义及基本术语.............................................................................................96
二叉树.....................................................................................................................99
6.2.1
二叉树的定义.................................................................................................99
6.2.2
二叉树的性质.................................................................................................99
6.2.3
二叉树的存储结构.......................................................................................101
二叉树基本操作的实现.......................................................................................105
树、森林...............................................................................................................112
6.4.1
树的存储结构...............................................................................................112
6.4.2
树、森林与二叉树的相互转换...................................................................114
6.4.3
树与森林的遍历...........................................................................................115
6.4.4
由遍历序列还原树结构...............................................................................116
Huffman树 ............................................................................................................117
6.5.1
二叉编码树...................................................................................................117
6.5.2
Huffman树及Huffman编码 ..........................................................................118
图...........................................................................................................................123
2
4.4
图的定义...............................................................................................................123
4.4.1
图及基本术语...............................................................................................123
4.4.2
抽象数据类型...............................................................................................127
4.5
图的存储方法.......................................................................................................129
4.5.1
邻接矩阵.......................................................................................................129
4.5.2
邻接表...........................................................................................................131
4.5.3
双链式存储结构...........................................................................................132
4.6
图ADT实现设计 ..................................................................................................138
4.7
图的遍历...............................................................................................................139
4.7.1
深度优先搜索...............................................................................................139
4.7.2
广度优先搜索...............................................................................................142
4.8
图的连通性...........................................................................................................143
4.8.1
无向图的连通分量和生成树.......................................................................143
4.8.2
有向图的强连通分量...................................................................................144
4.8.3
最小生成树...................................................................................................145
4.9
最短距离...............................................................................................................151
4.9.1
单源最短路径...............................................................................................151
4.9.2
任意顶点间的最短路径...............................................................................155
4.10
有向无环图及其应用...........................................................................................157
4.10.1
拓扑排序.......................................................................................................157
4.10.2
关键路径.......................................................................................................159
第八章
查找.......................................................................................................................164
8.1
查找的定义...........................................................................................................164
8.1.1
基本概念.......................................................................................................164
8.1.2
查找表接口定义...........................................................................................165
8.2
顺序查找与折半查找...........................................................................................165
8.3
查找树...................................................................................................................168
8.3.1
二叉查找树...................................................................................................168
8.3.2
AVL树 ...........................................................................................................175
8.3.3
B-树...............................................................................................................183
8.4
哈希.......................................................................................................................188
8.4.1
哈希表...........................................................................................................189
8.4.2
哈希函数.......................................................................................................190
8.4.3
冲突解决.......................................................................................................191
第九章
排序.......................................................................................................................194
9.1
排序的基本概念...................................................................................................194
9.2
插入类排序...........................................................................................................195
9.2.1
直接插入排序...............................................................................................195
9.2.2
折半插入排序...............................................................................................196
9.2.3
希尔排序.......................................................................................................197
9.3
交换类排序...........................................................................................................199
9.3.1
起泡排序.......................................................................................................199
9.3.2
快速排序.......................................................................................................200
9.4
选择类排序...........................................................................................................202
3
9.4.1
简单选择排序...............................................................................................202
9.4.2
树型选择排序...............................................................................................203
9.4.3
堆排序...........................................................................................................204
9.5
归并排序...............................................................................................................208
9.6
基于比较的排序的对比.......................................................................................209
9.7
在线性时间内排序...............................................................................................211
9.7.1
计数排序.......................................................................................................211
9.7.2
基数排序.......................................................................................................212
4
作者：周鹏
单位：三峡大学理学院
周
鹏
第一章 Java 与面向对象程序设计
在这一章中向读者简要介绍有关 Java 的基本知识。Java 语言是一种广泛使用并且具有
许多良好的如面向对象、可移植性、健壮性等特性的计算机高级程序设计语言，在这里对
Java 的介绍不可能面面俱到，
因此在第一章中只对理解书中 Java 代码的相关知识进行介绍。
对于熟悉 Java 的读者可以不阅读本章。
1.1 Java 语言基础知识
1.1.1 基本数据类型及运算
在 Java 中每个变量在使用前均必须声明它的类型。Java 共有八种基本数据类型：四种
是整型，两种浮点型，一种字符型以及用于表示真假的布尔类型。各种数据类型的细节如表
1-1 所示。
表 1-1 Java 数据类型
类型
存储空间
范围
int
32 bit
[-2147483648,2147483647]
short
16 bit
[-32768,32767]
long
64 bit
[-9223372036854775808, 9223372036854775807]
byte
8 bit
[-128,127]
float
32 bit
[-3.4E38,3.4E38]
double
64 bit
[-1.7E308,1.7E308]
char
16 bit
Unicode 字符
boolean
1 bit
True,false
在声明一个变量时，应先给出此变量的类型，随后写上变量名。在声明变量时一行中可
以有声明多个变量，并且可以在声明变量的同时对变量进行初始化。例如：
int i; double x, y = 1.2; char c = ‘z’; boolean flag;
在程序设计中，常常需要在不同的数字数据类型之间进行转换。图 1-1 给出了数字类型
间的合法转换。
1
char
byte
short
int
long
float
double
图 1-1 数字类型间的合法转换
图 1-1 中六个实箭头表示无信息损失的转换，
而三个虚箭头表示的转换则可能会丢失精
度。
有时在程序设计中也需要进行在图 1-1 中没有出现的转换，在 Java 中这种数字转换也
是可以进行的，
不过信息可能会丢失。
在可能丢失信息的情况下进行的转换是通过强制类型
转换来完成的。
其语法是在需要进行强制类型转换的表达式前使用圆括号，
圆括号中是需要
转换的目标类型。例如：
double x = 7.8; int n = (int)x;
//x 等于 7
Java 使用常见的算术运算符＋－*／进行加、减、乘、除的运算。当除法运算符／作用
于两个整数时，是进行整数除法。整数的模（即求余）运算使用 % 运算符。对整型变量一
种最常见的操作就是递增与递减运算， C/C++ 一样 Java 也支持递增和递减运算符。
与
例如： int n = 7, m = 2; double d = 7; n = n / m; d /= m; n--; int a = 2 * n++; int b = 2 * ++m;
//n 等于 3
//d 等于 3.5
//n 等于 2
//a 等于 4
//b 等于 6
此外 Java 还具有完备的关系运算符，如==（是否相等）,＜（小于）,＞（大于）,＜=
（小于等于）,＞=（大于等于）,!=（不等于）
；并且 Java 使用&&表示逻辑与，||表示逻辑
或，!表示逻辑非；以及七种位运算符&（与）
、|（或）
、^（异或）
、~（非） >>（右移）
、
、
>（高位填充 0 的右移）
。
最后 Java 还支持一种三元运算符 ?: ，这个运算符有时很有用。它的形式为 condition ? e1 : e2
这是一个表达式，在 condition 为 true 时返回值为 e1，否则为 e2。例如： min = x < y ? x : y;
则 min 为 x 与 y 中的较小值。
2
1.1.2 流程控制语句
计算机高级语言程序设计中共有三种流程结构，分别是：顺序、分支、循环。其中分支
与循环流程结构需要使用固定语法的流程控制语句来完成。
Java 中有两种语句可用于分支结构，
一种是 if 条件语句，
另一种是 switch 多选择语句。
条件语句的形式如下：
if (condition) statement1 else statement2
当 if 后的条件 condition 的值为 true 时执行 statement1 中的语句，否则执行 statement2
中的语句。
多选择语句的形式为： switch (integer expression) { case value1: block1; break; case value2: block2; break;
…
case valueN: blockN; break; default: default block;
}
switch 语句从与选择值相匹配的 case 标签处开始执行，
一直执行到下一个 break 处或者 switch 的末尾。如果没有相匹配的 case 标签，而且存在 default 子句，那么执行 default 子句。
如果没有相匹配的 case 标签，
并且没有 default 子句，
则结束 switch 语句的执行，
执行 switch
后面的语句。
Java 中的循环语句主要有三种，分别是 for 循环、while 循环、do…while 循环。 for 循环的形式为： for (initialization; condition; increment) statement; for 语句的循环控制的第一部分通常是对循环变量的初始化，第二部分给出进行循环的
测试条件，第三部分则是对循环变量的更新。
while 循环的形式为： while (condition) statement; while 循环首先对循环条件进行测试，只有在循环条件满足的情况下才执行循环体。 do…while 循环的形式为： do statement while (condition);
与 while 循环不同的是，do…while 循环首先执行一次循环体，当循环条件满足时则继
续进行下一次循环。
1.1.3 字符串
字符串是指一个字符序列。在 Java 中没有内置的字符串类型，而是在标准 Java 库中包
含一个名为 String 的预定义类。
每个被一对双引号括起来的字符序列均是 String 类的一个实
例。字符串可以使用如下方式定义。
3
String s1 = null;
//s1 指向 NULL
String s2 = "";
//s2 是一个不包含字符的空字符串
String s3 = "Hello";
Java 允许使用符号 ＋ 把两个字符串连接在一起。当连接一个字符串和一个非字符串
时，后者将被转换成字符串，然后进行连接。例如：
s3 = s3 + "World!";
//s3 为"HelloWorld!"
String s4 = "abc" + 123;
//s4 为"abc123"
Java 的 String 类包含许多方法，其中多数均非常有用，在表 1-2 中只给出最常用的一些
方法。
表 1-2 Java String 类常用方法
char charAt(int index)
Returns the char value at the specified index. int compareTo(String anotherString)
Compares two strings lexicographically. int compareToIgnoreCase(String str)
Compares two strings lexicographically, ignoring case differences. boolean endsWith(String suffix)
Tests if this string ends with the specified suffix. boolean equals(Object anObject)
Compares this string to the specified object. boolean equalsIgnoreCase(String anotherString)
Compares this String to another String, ignoring case considerations. int indexOf(String str)
Returns the index within this string of the first occurrence of the specified substring. int lastIndexOf(String str)
Returns the index within this string of the rightmost occurrence of the specified substring. int length()
Returns the length of this string. boolean startsWith(String prefix)
Tests if this string starts with the specified prefix. String substring(int beginIndex)
Returns a new string that is a substring of this string. String substring(int beginIndex, int endIndex)
Returns a new string that is a substring of this string. char[] toCharArray()
Converts this string to a new character array.
4
String toLowerCase()
Converts all of the characters in this String to lower case using the rules of the default locale.
String toString()
This object (which is already a string!) is itself returned.
String toUpperCase()
Converts all of the characters in this String to upper case using the rules of the default locale.
String trim()
Returns a copy of the string, with leading and trailing whitespace omitted.
如果读者需要进一步了解有关String提供的其他方法及方法完成的功能，可以通过在线
API（应用程序接口）文档了解相关信息，从中你可以查到标准库中所有的类及方法。API
文 档 是 Java SDK 的 一 部 分 ， 以 HTML 格 式 显 示 。 JDK1.5.0 的 API 文 档 地 址 为 ： http://java.sun.com/j2se/1.5.0/docs/api/index.html。 1.1.4 数组
数组是用来存放一组具有相同类型数据的数据结构。
可以通过整型下标来访问数组中的
每一个值。数组是可以通过在某种数据类型后面加上[]来定义，在此之后跟上变量名就可以
定义相应类型的数组变量了。例如： int[] a;
还可以使用另一种方法定义数组，例如：
int a[]；
以上这两种方法的定义是等价的。在这里只定义了一个整型数组变量 a，但是还没有将 a 真正的初始化为一个数组。为将一个数组初始化可以使用 new 关键字，也可以使用赋值语
句进行初始化。数组一旦被创建，就不能改变它的大小。
例如： a = new int[10];
//将 a 初始化为大小为 10 的整型数组。 int[] b = {0,1,2,3} //将 b 初始化为大小为 4 的整型数组，
//并且 4 个分量的值分别等于 0，1，2，3
数组的下标从 0 开始计数，到数组大小减 1 结束。在 Java 中不能越过数组下标的范围
去访问数组中的数据。例如：
a[10] = 10;
如果越过数组的下标访问数据，
则会产生一个名为 ArrayIndexOutOfBoundsException 的
运行时错误。
为避免产生这种错误，
可以通过在访问某个下标的数组元素前检查数组的大小
来避免。数组的大小可以通过数组的变量 length 返回。例如： for (int i=0;i 0
f (n ) =
f ' (0) n = 0
将 f(n) 与 f(n-1)代入原递推关系式，得到 g(n) g(n-1)…g(1) f’(n) = g(n) (g(n-1)…g(1) f’(n-1)) + h(n)
上式简化为
f’(n) = f’(n-1) + h(n)/ g(n) g(n-1)…g(1)
因此
f’(n) = f (0) +
'
n
∑ i =1
h (i) g(i) g(i - 1)...g(1)
最后求出
⎛
f(n) = g(n) g(n-1)…g(1) ⎜ f (0) +
⎜
⎝
n
∑ i =1
⎞ h (i)
⎟
g(i) g(i - 1)...g(1) ⎟
⎠
例 5-9 考虑例 5-4 中的递推关系 T(n) = 2T(n﹣1) + 2，T(1) = 2。
为方便求解可以引入T(0) = 0，令T(n) = 2n T’(n)，T(0)= T’(0)= 0。那么
2n T’(n) = 2 (2n-1 T’(n-1)) + 2
化简上式为
T’(n) = T’(n-1) + 2/2n
它的解是
n
T’(n) = T’(0) +
2
∑2 i =1
i
n
=
2
∑2 i =1
i
最后解出
86
T(n) = 2n T’(n) = 2n
n
2
∑2 i =1
i
= 2n+1-2
这与在例 5-4 中得到的结果是一致的。
例 5-10 求解递推关系 f(n) = n f(n-1) + n!，f(0) = 0。
令 f(n) = n! f’(n)，f(0) = f’(0)= 0。那么 n! f’(n) = n ((n-1)! f’(n-1)) + n!
化简上式为
f’(n) = f’(n-1) + 1
它的解是
f’(n) = f’(0) + n = n
最后解出
f(n) = n! f’(n) = nn!
5.3.4 Master Method
Master Method 为求解如下形式的递推式提供了简单的方法。
T(n) = aT(n/b) + f (n)
(5.1)
其中a、b为常数，并且a ≥ 1 , b > 1；f (n)是正的确定函数。
在 Master Method 中分 3 种不同的情况分别给出问题的解。(5.1)是一类分治法的时间复
杂性所满足的递归关系，即一个规模为 n 的问题被分成规模均为 n/b 的 a 个子间题，递归地
求解这 a 个子问题，然后通过对这 a 个子问题的解的综合，得到原问题的解。如果用 T(n)
表示规模为 n 的原问题的复杂性，用 f(n)表示把原问题分成 a 个子问题和将 a 个子问题的解
综合为原问题的解所需要的时间，我们便有递推关系式(5.1)。关于分治法的具体内容我们将
在 5.4 中作详细介绍。
Master Method 依赖于下面的定理 5.1
定理 5.1 设 a≥1 和 b>1 是常数，f (n)是定义在非负整数上的一个确定的非负函数。又设
T(n)也是定义在非负整数上的一个非负函数，且满足递推关系式(5.1)。递推关系式(5.1)中的
n/b 可以是 ⎣n / b⎦ ，也可以是 ⎡n / b⎤ 。那么我们有如下的 T(n)渐近估计式：
(
1.
对于某常数 ε>0，如果 f (n) = Ο n
2.
如果 f (n) = Θ n
3.
对于某常数 ε>0，
如果 f (n) = Ω n
(
log b a
log b a −ε
)，那么 T(n) = Θ(n ) log b a
) ，那么 T (n) = Θ(n
(
log b a +ε
log b a
log n
)
)，且对于某常数 c0
并且 a f (n/b) = 2 (n/4)log(n/4) = (1/2)n log n – n ≤(1/2)n log n = c f (n)，其中 c=1/21，则A，B和C可以分成 4 个大小为n/2 × n/2 的矩阵
⎛A
A = ⎜ 11
⎜A
⎝ 21
A 12 ⎞
⎛B
⎟ ， B = ⎜ 11
⎜B
⎟
A 22 ⎠
⎝ 21
B12 ⎞
⎛C
⎟ ， C = ⎜ 11
⎜C
⎟
B 22 ⎠
⎝ 21
C12 ⎞
⎟
C 22 ⎟
⎠
如果用分治法来计算矩阵 C，则可以进行如下计算
⎛ A B + A 12 B 21
C = ⎜ 11 11
⎜A B + A B
22 21
⎝ 21 11
A 11 B12 + A 12 B 22 ⎞
⎟
A 21 B12 + A 22 B 22 ⎟
⎠
划分步骤：将矩阵 A、B 分成 4 个 n/2 × n/2 的矩阵；
治理步骤：当 n>1 时，递归计算 8 个 n/2 × n/2 的矩阵的乘积；
组合步骤：计算治理步骤得到 n/2 × n/2 的矩阵的和。
在这里需要 8 次 n/2 × n/2 矩阵乘法和 4 次 n/2 × n/2 矩阵加法，
由此算法的时间复杂度可
以由下面的递推关系式表示
T(1) = 1
T(n) = 8T(n/2) +4(n/2) 2 n>1
由Master Method知T(n) = Θ(n3)，可见分治法并没有产生更有效的算法，相反使用分治
法它所消耗的时间比传统方法还要多，这主要是由分治法的递归调用引起的系统开销造成
的。
如果我们对这里分治法执行中所需的乘法与加法分开计算，
得到的结果与传统方法中使
用的乘法与加法的次数是一样的，
实际上这里的分治法不过是传统方法的递归形式罢了，
只
不过是矩阵元素相乘的次序上不同而已。
下面我们将寻找更有效的分治法来解决这个问题。
STRASSEN 算法
STRASSEN 算法与简单的分治法之间的区别在于它使用了 7 次 n/2 × n/2 矩阵乘法和 18
次 n/2 × n/2 矩阵加法。
我们仍然在当 n>1 时，将 A，B 和 C 可以分成 4 个大小为 n/2 × n/2 的矩阵
⎛A
A = ⎜ 11
⎜A
⎝ 21
A 12 ⎞
⎛B
⎟ ， B = ⎜ 11
⎜B
⎟
A 22 ⎠
⎝ 21
⎛C
C = ⎜ 11
⎜C
⎝ 21
C12 ⎞ ⎛ A 11 B11 + A 12 B 21
⎟=⎜
C 22 ⎟ ⎜ A 21 B11 + A 22 B 21
⎠ ⎝
B12 ⎞
⎟，
B 22 ⎟
⎠
92
A11 B12 + A12 B 22 ⎞
⎟
A 21 B12 + A 22 B 22 ⎟
⎠
为了计算 C，我们先计算以下 7 个 n/2 × n/2 矩阵的乘积 d1 = (A11 + A22) (B11 + B22) d2 = (A21 + A22) B11 d3 = A11 (B12 – B22) d4 = A22 (B21 – B11) d5 = (A11 + A12) B22 d6 = (A21 – A11) (B11 + B12) d7 = (A12 – A22) (B21 + B22)
然后可以通过下面公式求出 C
B
d3 + d5
⎛ d1 + d4 - d5 + d7
⎞
⎟
C=⎜
⎜ d2 + d4 d1 + d3 - d2 + d6 ⎟
⎝
⎠
此时算法的时间复杂度可以由下面的递推关系式表示
T(1) = 1
T(n) = 7T(n/2) +18(n/2)2
n>1
由Master Method知T(n) = Θ(nlog7)，在时间上的要优于传统方法。
5.4.3 选择问题
在具有 n 个元素的有序数组 a[0, n-1]中的中项是其中间元素。即如果 n 为奇数，则中间
元素是第(n+1)/2 个元素；
如果 n 为偶数则选择第 n/2 这个中间元素作为中项。
那么综合两种
情况，中项是第⎣(n+1)/2⎦个元素。
寻找中项或任意的第 k 小元素的一个直接方法是对所有的元素排序，并取出相应元素，
然而使用这种方法需要的时间较多，至少需要 Ω(n log n)时间，这是因为任何一种基于比较
的排序方法在最坏的情况下都需要这么多时间。
下面我们介绍一种使用分治法在 Θ(n)时间内就可以找到中项或第 k 小项的算法。在使
用分治法找出中项或第 k 小元素的基本思想是：
在分治法递归调用的每一个划分步骤中都舍
弃一定比例的元素，而在剩余的元素中寻找目标。于是问题的规模便以几何级数递减，例如
我们假设不管处理什么对象，算法都舍弃 1/4 的元素，而对剩余的 3/4 元素进行递归，那么
在第二次调用时元素的个数变为 3n/4，第三次调用时变为 9n/16，… 等等。现在假定在每
次调用中，算法对每个元素的处理时间不超过常数 c，则整个算法的运行时间为： cn + (3/4)cn + (3/4)2cn + … + (3/4)icn + …
这个几何级数的总和小于
∞
∑ cn(3 / 4)
i
= 4cn = Θ(n)
i =0
根据上面的思想方法，可以如下设计算法来寻找数组 a 的中项或第 k 小元素：
⑴ 当n ≤n0时，直接对数组排序，返回第k个元素即可，否则转⑵。
⑵ 把元素划分为 p = n/5 组，每组 5 个元素，不足 5 个元素的忽略。
⑶ 取每组的中项，构成一个规模为 p 的数组 M。
⑷ 对数组 M 递归求出其中项 mm。
⑸ 使用 mm 将原数组分成 3 部分：a1 存放小于 mm 的元素，a2 存放等于 mm 的元素，
93
a3 存放大于 mm 的元素。
⑹ 分三种情况分别处理 a1、a2、a3
如果|a1|≥k，对 a1 递归执行算法；否则
如果|a1|+|a2|≥k，mm 是第 k 小元素，返回；否则
对 a3 递归执行算法。
下面对以上步骤进行简要说明，
步骤⑵—⑷的作用主要是为了求出 p 个中项的中项 mm，
参见图 5-4。
Y mm X
箭头由小元素指向大元素
图 5-4 中项的中项 mm 的位置
于是我们知道矩形 X 中的元素均大于等于 mm，矩形 Y 中的元素均小于等于 mm。这
样在第⑸步中使用 mm 对数组 a 进行划分时，
可以保证 a1 与 a3 中的元素个数大约不会小于
数组 a 中元素个数的 1/4。最后导致在第⑹步中不论对 a1 或是 a3 进行递归时都可以保证至
少舍弃大约 1/4 左右的元素。
以上过程的具体实现如算法 5-7。
算法 5-7 selectK
输入：整数数组 a[0, n-1]
输出：a 中的第 k 小元素
代码：
public int selectK(int[] a, int n, int k){ if (n1，则其双亲结点 PARENT(i)是
结点 ⎣i / 2⎦ 。
⑵ 如果 2i>n，则结点 i 无左孩子；否则其左孩子是结点 2i。
⑶ 如果 2i+1>n，则结点 i 无右孩子；否则其右孩子是结点 2i+1。
100
证明： 先证明结论⑵、⑶。
当 i=1 时，由完全二叉树的定义知，如果 2i = 2 ≤ n，说明二叉树中存在两个或两个
以上结点，所以其左孩子的编号为 2；若 2>n，说明二叉树中不存在编号为 2 的结点，
因此它的左孩子不存在。同理如果 2i +1 = 3 ≤ n，说明二叉树中存在三个或三个以上结
点，所以其右孩子的编号为 3；若 3>n，说明二叉树中不存在编号为 3 的结点，因此它
的右孩子不存在。
当i>1 时： 若i是第j层的第一个结点，
①
则i=2j，
且其左孩子为j+1 层的第一个结点， j+1 j
编号为 2 = 2(2 ) = 2i，如果 2i>n，则无左孩子；其右孩子为j+1 层的第二个结点，编
号为 2i+1，
如果 2i+1>n，
则无右孩子。 ② 假设第j层上某个结点的编号为i， 2i+1 