文档介绍：选择排序SelectionSort(A[0..n-1])fori=0ton-2domin=iforj=i+1ton-1doifA[j]<A[min]min=jswapA[i]andA[min]冒泡排序BubbleSort(A[0..n-1])//输入:数组A,数组中的元素属于某偏序集//输出:按升序排列的数组A fori=0ton-2doforj=0ton-2-idoifA[j+1]<A[j]swapA[j]andA[j+1]改进的冒泡算法ALGORITHMBubbleSortImproved(A[0,…,n–1])//冒泡排序算法的改进//输入:数组A,数组中的元素属于某偏序集//输出:按升序排列的数组Afori←0ton–2do flag←True forj←0ton–2–ido ifA[j+1]<A[j] swap(A[j],A[j+1]) flag←False //如果在某一轮的比较中没有交换,则flag为True,算法结束 ifflag=Truereturn顺序查找算法算法SwquentialSearch2(A[0...n],k)//顺序查找算法的实现,它用了查找键来作限位器//输入:一个n个元素的数组A和一个查找键K//输出:第一个值等于K的元素的位置,如果找不到这样的元素就返回-1A[n]<--ki<--0whileA[i]!=Kdoi<--i+1ifi<nreturniElsereturn-1蛮力字符串匹配算法BruteForceStringMatch(T[0...n-1],P[0...m-1])//该算法实现了蛮力字符串匹配//输入:一个n个字符的数组T[0...n-1]代表一段文本//一个m个字符的数组P[0..m-1]代表一个模式//输出:如果查找成功的话,返回文本的第一个匹配字串中第一个字符的位置,//否则返回-1Fori<--0ton-mdoj<--0Whilej<mandP[j]=T[i+j]doj<--i+1Ifj=mreturnireturn-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>1copyA[0..ën/2û-1]toB[0..ën/2û-1]copyA[ën/2û..n-1]toC[0..ën/2û-1]MergeSort(B)MergeSort(C) Merge(B,C,A)两个数组合并的算法算法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;whilei<pandj<qdoifB[i]≤C[j]A[k]=B[i],i=i+1elseA[k]=C[j],j=j+1k=k+1ifi=pcopyC[j..q-1]toA[k..p+q-1