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

《算法设计与分析部分算法伪代码.docx》由会员分享，可在线阅读，更多相关《算法设计与分析部分算法伪代码.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法设计与分析部分算法伪代码 第三章蛮力法 1.选择排序 ?SelectionSort(A0.n-1) for i=0 to n-2 do min=i for j=i+1 to n-1 do if Aj min=j swap Ai and Amin 2.冒泡排序 ?BubbleSort(A0.n-1) / 输入：数组A，数组中的元素属于某偏序集 / 输出：按升序排列的数组A for i=0 to n-2 do for j=0 to n-2-i do if Aj+1 3.改进的冒泡算法 ?ALGORITHM BubbleSortImproved( A0,n 1 ) / 冒泡排序算法的改进 / 输

2、入：数组A，数组中的元素属于某偏序集 / 输出：按升序排列的数组A for i 0 to n 2 do flag True for j 0 to n 2 i do if Aj+1 1 copy A0.?n/2?-1 to B0.?n/2?-1 copy A?n/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中已经有序存

3、放了B和C中的元素 i=0,j=0,k=0; while i 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 快速排序算法 QuickSort(Al.r) / 使用快速排序法对序列或者子序列排序 / 输入：子序列Al.r或者序列本身A0.n-1 / 输出：非递减序列A if l temp do Aj+1 Aj j j 1 Aj+1 temp 深度优先查找 算法BFS（G） /实现给定图的深度优先查找遍历 /输入：图G= /输出：图G的

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

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

6、e 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 拓扑排序 第六章变治法 Gauss消去法 ?GaussElimination(A1.n, b1.n) / 输入：系数矩阵A及常数项b / 输出：方程组的增广

7、矩阵等价的上三角矩阵 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-1次删除堆的根结点的操作，把删除得到的结点保存在给定数组中。 ? 1 构造堆的效率是多少？ ?O(n) ? 2 推排序的效率 ?O(nlogn) Horner法则 第七章时空权衡 计数排序 比较计数算法 算法ComparisonCountingSort(A0.n-1) /用比较计数法对数组排序 /输入：可排序数组

8、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 ifAi Countj=Countj+1 Else Counti=Counti+1 For i=0 to n-1 do SCounti=Ai Return S C(n)=n(n-1)/2 第八章动态规划 WARSHALL算法 ?void WARSHALL（m） for (i=1; in; i+ ) for (j1; jn; j+ ) if(m j，iT) for (k=1; in; i+ ) m j，k + m i，k; (4) ?该算法由邻接矩阵在原矩阵构建传递闭包 ?WARSHALL算法的时间复杂度为O(n3)。Floyd算法 ?算法Floyd(W1.n,1.n) / 实现计算完全最短路径的Floyd算法 / 输入：图的权重矩阵W / 输出：包含最短路径长度的距离矩阵