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

1、第三章 蛮力法1. 选择排序n selectionsort(a0.n-1) for i=0 to n-2 do min=i for j=i+1 to n-1 do if ajamin min=j swap ai and amin2. 冒泡排序n bubblesort(a0.n-1)/ 输入：数组a，数组中的元素属于某偏序集/ 输出：按升序排列的数组a for i=0 to n-2 do for j=0 to n-2-i do if aj+1aj swap aj and aj+13. 改进的冒泡算法n algorithm bubblesortimproved( a0,n 1 )/ 冒泡排序算法的

2、改进/ 输入：数组a，数组中的元素属于某偏序集/ 输出：按升序排列的数组afor i 0 to n 2 doflag true for j 0 to n 2 i doif aj+1 ajswap(aj, aj+1)flag false / 如果在某一轮的比较中没有交换，则flag为true，算法结束if flag = true return4. 顺序查找算法 算法 swquentialsearch2(a0.n,k) /顺序查找算法的实现，它用了查找键来作限位器 /输入：一个n个元素的数组a和一个查找键k /输出：第一个值等于k的元素的位置，如果找不到这样的元素就返回 -1 an-k i-0wh

3、ile ai!=k do i-i+1if in return ielse return -15. 蛮力字符串匹配 算法 bruteforcestringmatch(t0.n-1,p0.m-1) /该算法实现了蛮力字符串匹配 /输入：一个n个字符的数组t0.n-1代表一段文本 / 一个m个字符的数组p0.m-1代表一个模式 /输出：如果查找成功的话，返回文本的第一个匹配字串中第一个字符的位置， / 否则返回-1 for i-0 to n-m do j-0while jm and pj=ti+jdo j 1 copy a0.n/2-1 to b0.n/2-1 copy an/2.n-1 to c0

4、.n/2-1 mergesort( b ) mergesort( c ) merge( b,c,a ) 两个数组合并的算法算法 merge(b0.p-1,c0.q-1,a0.p+q-1) /将两个有序数组合并成一个有序的数组 /输入：两个有序数组b0.p-1和c0.q-1 /输出：a0.p+q-1中已经有序存放了b和c中的元素 i=0,j=0,k=0; while ip and jq do if bicj ak=bi, i=i+1 else ak=cj, j=j+1 k=k+1 if i=p copy cj.q-1 to ak.p+q-1 else copy bi.p-1 to a0.p+q-

5、1快速排序算法nquicksort(al.r) / 使用快速排序法对序列或者子序列排序 / 输入：子序列al.r或者序列本身a0.n-1 / 输出：非递减序列a if l r s partition( al.r ) quicksort( al.s-1 ) quicksort( as+1.r )/s是中轴元素/基准点，是数组分区位置的标志实现分区的算法n算法 partition( al.r ) / 输入：子数组al.r / 输出：分裂点/基准点pivot的位置 p ali l; j r+1 repeat repeati i + 1until ai p repeat j j 1 until aj

6、p swap( ai, aj ) until i j swap( ai, aj ) swap( al, aj ) return j折半查找n binarysearch( a0.n-1, k ) / 输入：已排序大小为n的序列a，待搜索对象k / 输出：如果搜索成功，则返回k的位置，否则返回-1 l=0,r=n-1; while lr mid= (l+r)/2 if k = amid return mid else if k temp doaj+1 ajj j 1aj+1 temp深度优先查找算法 bfs（g）/实现给定图的深度优先查找遍历/输入：图g=/输出：图g的顶点，按照被dfs遍历第一次

7、访问到的先后次序，用连续的整数标记，将v中的每个顶点标记为0，表示还“未访问”count =0/记录这是第几个访问的节点mark each vertex with 0/标记为 unvisitedfor each vertex v v doif v is marked with 0 dfs(v)dfs(v)/递归访问所有和v相连接的未访问顶点，然后按照全局变量count的值/根据遇到它们的先后顺序，给它们附上相应的数字count = count + 1mark v with countfor each vertex w adjacent to v doif w is marked with 0

8、dfs(w)广度优先n bfs(g) /实现给定图的深度优先查找遍历/输入：图g=/输出：图g的顶点，按照被bfs遍历第一次访问到的先后次序，用连续的整数标记，将v中的每个顶点标记为0，表示还“未访问” count =0 mark each vertex with 0 for each vertex v v do bfs(v)bfs(v)/递归访问所有和v相连接的未访问顶点，然后按照全局变量count的值/根据遇到它们的先后顺序，给它们附上相应的数字count = count + 1mark v with countinitialize queue with vwhile queue is n

9、ot empty doa = front of queuefor each vertex w adjacent to a doif w is marked with 0 count = count + 1mark w with countadd w to the end of the queueremove a from the front of the queue拓扑排序第六章 变治法gauss消去法n gausselimination(a1.n, b1.n) / 输入：系数矩阵a及常数项 b / 输出：方程组的增广矩阵等价的上三角矩阵 for i=1 to n do ain+1 =bi f

10、or j= i+1 to n do for k = i to n+1 do ajk = ajk aik*aji/aii堆排序n 堆排序主要包括两个步骤：q 对于给定的数组构造相应的堆。q 对所构造的堆执行n-1次删除堆的根结点的操作，把删除得到的结点保存在给定数组中。 n 1 构造堆的效率是多少？q o(n)n 2 推排序的效率q o(nlogn)horner法则第7章 时空权衡 计数排序比较计数算法算法 comparisoncountingsort(a0.n-1) /用比较计数法对数组排序 /输入：可排序数组a0.n-1 /输出：将a中的元素按照升序排列的数组s0.n-1 for i=0 to n-1 do counti=0 for i=0 to n-2 do for j=i+1 to n-1 do ifaiaj countj=countj+1else counti=counti+1for i=0 to n-1 do scounti=ai return sc(n)=n(n-1)/2第八章 动态规划warshall算法n void warshall（m）for (i=1; i n; i+ )for (j1; j n; j+ )if(