算法設(shè)計(jì)與分析部分算法偽代碼

《算法設(shè)計(jì)與分析部分算法偽代碼》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

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

2、n–1])//冒泡排序算法的改進(jìn)//輸入：數(shù)組A，數(shù)組中的元素屬于某偏序集//輸出：按升序排列的數(shù)組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)兩個(gè)數(shù)組合并的算法算法Merge(B[0..p-1],C[0..q-1],A[0..p+q-1])//將兩個(gè)有序數(shù)組合并成一個(gè)有序的數(shù)組//輸入：兩個(gè)有序數(shù)組B[0...p-1]和C[0...q-1]//輸出：A[0..p+q-1]中已經(jīng)有序存放了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])//使用快速排序法對(duì)序列或者子序列排序//輸入：子序列A[l..r]或者序列本身A[0..n-1]//輸出：非遞減序列Aifl

7、志實(shí)現(xiàn)分區(qū)的算法n算法Partition(A[l..r])//輸入：子數(shù)組A[l..r]//輸出：分裂點(diǎn)/基準(zhǔn)點(diǎn)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，待搜索對(duì)象k//輸出：如果搜索成功，則返回k的位置，否則

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