算法设计与分析部分算法伪代码.doc

文档介绍：第三章蛮力法
选择排序
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]<A[min]
min=j
swap A[i] and A[min]
冒泡排序
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]<A[j] swap A[j] and A[j+1]
改进的冒泡算法
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] < A[j]
swap(A[j], A[j+1])
flag ← False
// 如果在某一轮的比较中没有交换,则flag为True,算法结束
if flag = True return
顺序查找算法
算法 SwquentialSearch2(A[0...n],k)
//顺序查找算法的实现,它用了查找键来作限位器
//输入:一个n个元素的数组A和一个查找键K
//输出:第一个值等于K的元素的位置,如果找不到这样的元素就返回-1
A[n]<--k
i<--0
while A[i]!=K do
i<--i+1
if i<n return i
Else return -1
蛮力字符串匹配
算法 BruteForceStringMatch(T[0...n-1],P[0...m-1])
//该算法实现了蛮力字符串匹配
//输入:一个n个字符的数组T[0...n-1]代表一段文本
// 一个m个字符的数组P[0..m-1]代表一个模式
//输出:如果查找成功的话,返回文本的第一个匹配字串中第一个字符的位置,
// 否则返回-1
For i<--0 to n-m do
j<--0
While j<m and P[j]=T[i+j]do
j<--i+1
If j=m return i
return -1
合并排序最差Θ(nlog2n)
快速排序最优Θ(nlog2n)
最差Θ(n2)
平均Θ()
选择排序 Θ(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] t