第三章 蛮力法
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] 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] 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 ** ** 4. 顺序查找算法 算法 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 算法 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 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 < r 实现分区的算法 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 < A[mid] r=m-1 else l=m+1 return -1 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] C(n)=n(n-1)/2 第八章 动态规划 WARSHALL算法 void WARSHALL（m） for (i=1; i<＝ n; i++ ) for (j＝1; j<＝ n; j++ ) if(m [j，i]＝T) for (k=1; i<＝ n; i++ ) m [j，k] + ＝m [i，k]; (4) 该算法由邻接矩阵在原矩阵构建传递闭包 WARSHALL算法的时间复杂度为O(n3)。 Floyd算法 算法 Floyd(W[1..n,1..n]) // 实现计算完全最短路径的Floyd算法 // 输入：图的权重矩阵W // 输出：包含最短路径长度的距离矩阵 ** ** ** 因篇幅问题不能全部显示，请点此查看更多更全内容