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

《算法设计与分析部分算法伪代码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章蛮力法1.选择排序nSelectionSort(A[0..n-1])fori=0ton-2domin=iforj=i+1ton-1doifA[j]

2、n–1])//冒泡排序算法的改进//输入：数组A，数组中的元素属于某偏序集//输出：按升序排列的数组Afori←0ton–2doflag←Trueforj←0ton–2–idoifA[j+1]

3、等于K的元素的位置，如果找不到这样的元素就返回-1A[n]<--ki<--0whileA[i]!=Kdoi<--i+1ifi

4、--0Whilej1cop

5、yA[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

6、]=B[i],i=i+1elseA[k]=C[j],j=j+1k=k+1ifi=pcopyC[j..q-1]toA[k..p+q-1]elsecopyB[i..p-1]toA[0..p+q-1]快速排序算法nQuickSort(A[l..r])//使用快速排序法对序列或者子序列排序//输入：子序列A[l..r]或者序列本身A[0..n-1]//输出：非递减序列Aifl

7、志实现分区的算法n算法Partition(A[l..r])//输入：子数组A[l..r]//输出：分裂点/基准点pivot的位置p←A[l]　i←l;j←r+1repeatrepeat　i←i+1　untilA[i]≥prepeatj←j–1untilA[j]≤pswap(A[i],A[j])untili≥j　　swap(A[i],A[j])　swap(A[l],A[j])returnj折半查找nBinarySearch(A[0..n-1],k)//输入：已排序大小为n的序列A，待搜索对象k//输出：如果搜索成功，则返回k的位置，否则

8、返回-1l=0,r=n-1;Whilel≤rmid=ë(l+r)/2ûifk=A[mid]returnmidelseifk