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

第三章 蛮力法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 )/ 冒泡排序算法的改进/ 输入：数组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-0while 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.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-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 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遍历第一次访问到的先后次序，用连续的整数标记，将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 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 not 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 for 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(m