第三章 蛮力法
1. 选择排序
⏹ SelectionSort(A[0..n-1]) for i=0 to n-2 do min=i
for j=i+1 to n-1 do if A[j]
2. 冒泡排序
⏹ BubbleSort(A[0..n-1])
// 输入：数组A ，数组中的元素属于某偏序集 // 输出：按升序排列的数组A
for i=0 to n-2 do
for j=0 to n-2-i do
if A[j+1]
3. 改进的冒泡算法
⏹ ALGORITHM BubbleSortImproved( A[0,…,n – 1] ) // 冒泡排序算法的改进
// 输入：数组A ，数组中的元素属于某偏序集 // 输出：按升序排列的数组A for i ← 0 to n – 2 do
flag ← True
for j ← 0 to n – 2 – i do
if A[j+1]
swap(A[j], A[j+1]) flag ← False
// 如果在某一轮的比较中没有交换，则flag 为True ，算法结束 if flag = True return
4. 顺序查找算法
算法 SwquentialSearch2(A[0...n],k)
//顺序查找算法的实现，它用了查找键来作限位器 //输入：一个n 个元素的数组A 和一个查找键K
//输出：第一个值等于K 的元素的位置，如果找不到这样的元素就返回 -1 A[n]
while A[i]!=K do i
5. 蛮力字符串匹配
算法 BruteForceStringMatch(T[0...n-1],P[0...m-1]) //该算法实现了蛮力字符串匹配
//输入：一个n 个字符的数组T[0...n-1]代表一段文本
// 一个m 个字符的数组P[0..m-1]代表一个模式
//输出：如果查找成功的话，返回文本的第一个匹配字串中第一个字符的位置， // 否则返回-1 For i
While j
j
If j=m return i return -1
⏹ 合并排序最差Θ(nlog2n) ⏹ 快速排序最优Θ(nlog2n) 最差Θ(n2) 平均Θ(1.38nlog2n)
⏹ 选择排序 Θ(n2) ⏹ 冒泡排序 Θ(n2)
⏹ 插入排序最差Θ(n2) ⏹ 最优 Θ(n) ⏹ 平均 Θ(n2)
第四章 分治法
合并排序
算法 MergeSort(A[0..n-1] )
// 递归调用mergesort 来对数组 A[0...n-1] 排序 // 输入：一个可排序数组A[0..n-1] // 输出：非降序排列的数组A[0..n-1]
if n > 1
copy A[0..⎣n/2⎦-1] to B[0..⎣n/2⎦-1] copy A[⎣n/2⎦..n-1] to C[0..⎣n/2⎦-1] MergeSort( B ) MergeSort( C )
两个数组合并的算法
算法 Merge (B[0..p-1],C[0..q-1],A[0..p+q-1]) //将两个有序数组合并成一个有序的数组 //输入：两个有序数组B[0...p-1]和C[0...q-1]
//输出：A[0..p+q-1]中已经有序存放了B 和C 中的元素 i=0,j=0,k=0; while i
A[k]=C[j], j=j+1 k=k+1 if i=p
copy C[j..q-1] to A[k..p+q-1] else
copy B[i..p-1] to A[0..p+q-1]
Merge( B,C,A )
快速排序算法 QuickSort(A[l..r])
// 使用快速排序法对序列或者子序列排序 // 输入：子序列A[l..r]或者序列本身A[0..n-1] // 输出：非递减序列A if l
实现分区的算法
Partition( A[l..r] ) // 输入：子数组A[l..r]
// 输出：分裂点/基准点pivot 的位置 p ← A[l] i ← l; j ← r+1 repeat
repeat i ←i + 1 until A[i] ≥ p
repeat j ← j – 1 until A[j] ≤ p swap( A[i], A[j] ) until i ≥ j swap( A[i], A[j] ) swap( A[l], A[j] ) return j 折半查找
BinarySearch( A[0..n-1], k )
// 输入：已排序大小为n 的序列A ，待搜索对象k // 输出：如果搜索成功，则返回k 的位置，否则返回-1 l=0,r=n-1; While l≤r
mid= ⎣(l+r)/2⎦ if k = A[mid] return mid else if k
s ← Partition( A[l..r] ) QuickSort( A[l..s-1] ) QuickSort( A[s+1..r] )
//s是中轴元素/基准点，是数组分区位置的标志
Strassen 矩阵
⏹ Strassen 方法 M1=A11(B12-B22) M2=(A11+A12)B22 M3=(A21+A22)B11 M4=A22(B21-B11) M5=(A11+A22)(B11+B22) M6=(A12-A22)(B21+B22)
M7=(A11-A21)(B11+B12)
第五章 减治法
插入排序
⏹ ALGORITHM InsertionSort( A[0..n-1] ) // 对给定序列进行直接插入排序 // 输入：大小为n 的无序序列A // 输出：按非递减排列的序列A for i ← 1 to n-1 do
temp ← A[i] j ← i-1
while j ≥ 0 and A[j] > temp do
深度优先查找 算法 BFS （G ）
//实现给定图的深度优先查找遍历 //输入：图G=
每个顶点标记为0，表示还“未访问” count =0//记录这是第几个访问的节点 mark each vertex with 0//标记为 unvisited for each vertex v∈ V do if v is marked with 0 dfs(v)
//输出：图G 的顶点，按照被DFS 遍历第一次访问到的先后次序，用连续的整数标记，将V 中的
A[j+1] ← A[j] j ← j –1
A[j+1] ←temp
dfs(v )
//递归访问所有和v 相连接的未访问顶点，然后按照全局变量count 的值 //根据遇到它们的先后顺序，给它们附上相应的数字 count = count + 1 mark v with count
for each vertex w adjacent to v do if w is marked with 0 dfs(w ) 广度优先 BFS(G)
/实现给定图的深度优先查找遍历 //输入：图G=
每个顶点标记为0，表示还“未访问”
count =0
mark each vertex with 0 for each vertex v∈ V do bfs(v) bfs(v)
//递归访问所有和v 相连接的未访问顶点，然后按照全局变量count 的值 //根据遇到它们的先后顺序，给它们附上相应的数字 count = count + 1 mark v with count initialize queue with v while queue is not empty do a = front of queue
for each vertex w adjacent to a do if w is marked with 0 count = count + 1 mark w with count
add w to the end of the queue remove a from the front of the queue 拓扑排序
//输出：图G 的顶点，按照被BFS 遍历第一次访问到的先后次序，用连续的整数标记，将V 中的
第六章 变治法
Gauss 消去法
⏹ GaussElimination(A[1..n], b[1..n]) // 输入：系数矩阵A 及常数项 b
// 输出：方程组的增广矩阵等价的上三角矩阵 for i=1 to n do A[i][n+1] =b[i]
for j= i+1 to n do for k = i to n+1 do
A[j][k] = A[j][k] – A[i][k]*A[j][i]/A[i][i] 堆排序
⏹ 堆排序主要包括两个步骤：
❑ 对于给定的数组构造相应的堆。
❑ 对所构造的堆执行n-1次删除堆的根结点的操作，把删除得到的结点保存在给定数
组中。
⏹ 1 构造堆的效率是多少？
❑ O(n)
⏹ 2 推排序的效率
❑ O(nlogn)
Horner 法则
第七章 时空权衡 计数排序
比较计数算法
算法 ComparisonCountingSort(A[0...n-1]) //用比较计数法对数组排序 //输入：可排序数组A[0...n-1]
//输出：将A 中的元素按照升序排列的数组S[0..n-1] For i=0 to n-1 do count[i]=0 For i=0 to n-2 do For j=i+1 to n-1 do ifA[i]
Count[j]=Count[j]+1 Else Count[i]=Count[i]+1 For i=0 to n-1 do S[Count[i]]=A[i] Return S
C(n)=n(n-1)/2
第八章 动态规划
WARSHALL 算法
⏹ void WARSHALL（m ） for (i=1; i
for (j＝1; j
if(m [j，i]＝T)
for (k=1; i
m [j，k] + ＝m [i，k]; (4)
⏹ 该算法由邻接矩阵在原矩阵构建传递闭包 ⏹ WARSHALL 算法的时间复杂度为O(n3)。 Floyd 算法
⏹ 算法 Floyd(W [1..n ,1.. n ])
// 实现计算完全最短路径的Floyd 算法 // 输入：图的权重矩阵W
// 输出：包含最短路径长度的距离矩阵
第三章 蛮力法
1. 选择排序
⏹ SelectionSort(A[0..n-1]) for i=0 to n-2 do min=i
for j=i+1 to n-1 do if A[j]
2. 冒泡排序
⏹ BubbleSort(A[0..n-1])
// 输入：数组A ，数组中的元素属于某偏序集 // 输出：按升序排列的数组A
for i=0 to n-2 do
for j=0 to n-2-i do
if A[j+1]
3. 改进的冒泡算法
⏹ ALGORITHM BubbleSortImproved( A[0,…,n – 1] ) // 冒泡排序算法的改进
// 输入：数组A ，数组中的元素属于某偏序集 // 输出：按升序排列的数组A for i ← 0 to n – 2 do
flag ← True
for j ← 0 to n – 2 – i do
if A[j+1]
swap(A[j], A[j+1]) flag ← False
// 如果在某一轮的比较中没有交换，则flag 为True ，算法结束 if flag = True return
4. 顺序查找算法
算法 SwquentialSearch2(A[0...n],k)
//顺序查找算法的实现，它用了查找键来作限位器 //输入：一个n 个元素的数组A 和一个查找键K
//输出：第一个值等于K 的元素的位置，如果找不到这样的元素就返回 -1 A[n]
while A[i]!=K do i
5. 蛮力字符串匹配
算法 BruteForceStringMatch(T[0...n-1],P[0...m-1]) //该算法实现了蛮力字符串匹配
//输入：一个n 个字符的数组T[0...n-1]代表一段文本
// 一个m 个字符的数组P[0..m-1]代表一个模式
//输出：如果查找成功的话，返回文本的第一个匹配字串中第一个字符的位置， // 否则返回-1 For i
While j
j
If j=m return i return -1
⏹ 合并排序最差Θ(nlog2n) ⏹ 快速排序最优Θ(nlog2n) 最差Θ(n2) 平均Θ(1.38nlog2n)
⏹ 选择排序 Θ(n2) ⏹ 冒泡排序 Θ(n2)
⏹ 插入排序最差Θ(n2) ⏹ 最优 Θ(n) ⏹ 平均 Θ(n2)
第四章 分治法
合并排序
算法 MergeSort(A[0..n-1] )
// 递归调用mergesort 来对数组 A[0...n-1] 排序 // 输入：一个可排序数组A[0..n-1] // 输出：非降序排列的数组A[0..n-1]
if n > 1
copy A[0..⎣n/2⎦-1] to B[0..⎣n/2⎦-1] copy A[⎣n/2⎦..n-1] to C[0..⎣n/2⎦-1] MergeSort( B ) MergeSort( C )
两个数组合并的算法
算法 Merge (B[0..p-1],C[0..q-1],A[0..p+q-1]) //将两个有序数组合并成一个有序的数组 //输入：两个有序数组B[0...p-1]和C[0...q-1]
//输出：A[0..p+q-1]中已经有序存放了B 和C 中的元素 i=0,j=0,k=0; while i
A[k]=C[j], j=j+1 k=k+1 if i=p
copy C[j..q-1] to A[k..p+q-1] else
copy B[i..p-1] to A[0..p+q-1]
Merge( B,C,A )
快速排序算法 QuickSort(A[l..r])
// 使用快速排序法对序列或者子序列排序 // 输入：子序列A[l..r]或者序列本身A[0..n-1] // 输出：非递减序列A if l
实现分区的算法
Partition( A[l..r] ) // 输入：子数组A[l..r]
// 输出：分裂点/基准点pivot 的位置 p ← A[l] i ← l; j ← r+1 repeat
repeat i ←i + 1 until A[i] ≥ p
repeat j ← j – 1 until A[j] ≤ p swap( A[i], A[j] ) until i ≥ j swap( A[i], A[j] ) swap( A[l], A[j] ) return j 折半查找
BinarySearch( A[0..n-1], k )
// 输入：已排序大小为n 的序列A ，待搜索对象k // 输出：如果搜索成功，则返回k 的位置，否则返回-1 l=0,r=n-1; While l≤r
mid= ⎣(l+r)/2⎦ if k = A[mid] return mid else if k
s ← Partition( A[l..r] ) QuickSort( A[l..s-1] ) QuickSort( A[s+1..r] )
//s是中轴元素/基准点，是数组分区位置的标志
Strassen 矩阵
⏹ Strassen 方法 M1=A11(B12-B22) M2=(A11+A12)B22 M3=(A21+A22)B11 M4=A22(B21-B11) M5=(A11+A22)(B11+B22) M6=(A12-A22)(B21+B22)
M7=(A11-A21)(B11+B12)
第五章 减治法
插入排序
⏹ ALGORITHM InsertionSort( A[0..n-1] ) // 对给定序列进行直接插入排序 // 输入：大小为n 的无序序列A // 输出：按非递减排列的序列A for i ← 1 to n-1 do
temp ← A[i] j ← i-1
while j ≥ 0 and A[j] > temp do
深度优先查找 算法 BFS （G ）
//实现给定图的深度优先查找遍历 //输入：图G=
每个顶点标记为0，表示还“未访问” count =0//记录这是第几个访问的节点 mark each vertex with 0//标记为 unvisited for each vertex v∈ V do if v is marked with 0 dfs(v)
//输出：图G 的顶点，按照被DFS 遍历第一次访问到的先后次序，用连续的整数标记，将V 中的
A[j+1] ← A[j] j ← j –1
A[j+1] ←temp
dfs(v )
//递归访问所有和v 相连接的未访问顶点，然后按照全局变量count 的值 //根据遇到它们的先后顺序，给它们附上相应的数字 count = count + 1 mark v with count
for each vertex w adjacent to v do if w is marked with 0 dfs(w ) 广度优先 BFS(G)
/实现给定图的深度优先查找遍历 //输入：图G=
每个顶点标记为0，表示还“未访问”
count =0
mark each vertex with 0 for each vertex v∈ V do bfs(v) bfs(v)
//递归访问所有和v 相连接的未访问顶点，然后按照全局变量count 的值 //根据遇到它们的先后顺序，给它们附上相应的数字 count = count + 1 mark v with count initialize queue with v while queue is not empty do a = front of queue
for each vertex w adjacent to a do if w is marked with 0 count = count + 1 mark w with count
add w to the end of the queue remove a from the front of the queue 拓扑排序
//输出：图G 的顶点，按照被BFS 遍历第一次访问到的先后次序，用连续的整数标记，将V 中的
第六章 变治法
Gauss 消去法
⏹ GaussElimination(A[1..n], b[1..n]) // 输入：系数矩阵A 及常数项 b
// 输出：方程组的增广矩阵等价的上三角矩阵 for i=1 to n do A[i][n+1] =b[i]
for j= i+1 to n do for k = i to n+1 do
A[j][k] = A[j][k] – A[i][k]*A[j][i]/A[i][i] 堆排序
⏹ 堆排序主要包括两个步骤：
❑ 对于给定的数组构造相应的堆。
❑ 对所构造的堆执行n-1次删除堆的根结点的操作，把删除得到的结点保存在给定数
组中。
⏹ 1 构造堆的效率是多少？
❑ O(n)
⏹ 2 推排序的效率
❑ O(nlogn)
Horner 法则
第七章 时空权衡 计数排序
比较计数算法
算法 ComparisonCountingSort(A[0...n-1]) //用比较计数法对数组排序 //输入：可排序数组A[0...n-1]
//输出：将A 中的元素按照升序排列的数组S[0..n-1] For i=0 to n-1 do count[i]=0 For i=0 to n-2 do For j=i+1 to n-1 do ifA[i]
Count[j]=Count[j]+1 Else Count[i]=Count[i]+1 For i=0 to n-1 do S[Count[i]]=A[i] Return S
C(n)=n(n-1)/2
第八章 动态规划
WARSHALL 算法
⏹ void WARSHALL（m ） for (i=1; i
for (j＝1; j
if(m [j，i]＝T)
for (k=1; i
m [j，k] + ＝m [i，k]; (4)
⏹ 该算法由邻接矩阵在原矩阵构建传递闭包 ⏹ WARSHALL 算法的时间复杂度为O(n3)。 Floyd 算法
⏹ 算法 Floyd(W [1..n ,1.. n ])
// 实现计算完全最短路径的Floyd 算法 // 输入：图的权重矩阵W
// 输出：包含最短路径长度的距离矩阵