文档介绍：第三章蛮力法 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]<A[min] min=j swap A[i] and A[min] 2. 冒泡排序? 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] 3. 改进的冒泡算法? ALGORITHM BubbleSortImproved( A[0, …,n– 1]) // 冒泡排序算法的改进// 输入:数组 A ,数组中的元素属于某偏序集// 输出:按升序排列的数组 A for i←0 ton–2 do flag ← True for j←0 ton–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<n return i Else return -1 5. 蛮力字符串匹配算法 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] ifn>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,C,A ) 两个数组合并的算法算法 Merg