南京工程高等職業(yè)學(xué)校畢業(yè)設(shè)計開題報告題目名稱：關(guān)于FORTRAN搜索與排序算法學(xué)生名稱：張智杰學(xué)號：5系部：信息科學(xué)系專業(yè)：計算機應(yīng)用技術(shù)班級：J04005指導(dǎo)教師：王正友職稱：講師2009年6月6月摘要FORTRAN,亦譯為福傳，是英文“FORmulaTRANslator”的縮寫，譯為“公式翻譯器”，它是世界上最早出現(xiàn)的計算機高級程序設(shè)計語言，廣泛應(yīng)用于科學(xué)和工程計算領(lǐng)域。FORTRAN語言以其特有的功能在數(shù)值、科學(xué)和工程計算領(lǐng)域發(fā)揮著重要作用。Fortran語言的最大特性是接近數(shù)學(xué)公式的自然描述，在計算機里具有很高的執(zhí)行效率。易學(xué)，語法嚴(yán)謹(jǐn)?？梢灾苯訉仃嚭蛷?fù)數(shù)進行運算，這一點類似matlab。自誕生以來廣泛地應(yīng)用于數(shù)值計算領(lǐng)域，積累了大量高效而可靠的源程序。很多專用的大型數(shù)值運算計算機針對Fortran做了優(yōu)化。廣泛地應(yīng)用于并行計算和高性能計算領(lǐng)域。Fortran90，F(xiàn)ortran95，F(xiàn)ortran2003的相繼推出使Fortran語言具備了現(xiàn)代高級編程語言的一些特性。所以，再此我們主要討論fortran語言的基礎(chǔ)，搜索與排序算法的種類與最簡代碼形式。關(guān)鍵字：FORTRAN，順序搜索，二分搜索，散列搜索，冒泡法等目錄TOC\o"1-5"\h\z\o"CurrentDocument"順序搜索4\o"CurrentDocument"二分搜索8散列排序11\o"CurrentDocument"冒泡法14\o"CurrentDocument"選擇排序法1519快速排序法191.順序搜索-順序搜索是最簡單的一種搜索算法，簡單來說，就是將數(shù)據(jù)依次拿出來查找看是否有符合要求的結(jié)果。例如對于一組數(shù)據(jù)(n1,n2,n3,…,nn)，想要確定其中是否有數(shù)據(jù)m，則順序搜索的做法如下：-先看第一個數(shù)據(jù)n1，如果n1=m則找到了所要找的數(shù)據(jù)，否則繼續(xù)搜索；-接著看第二個數(shù)據(jù)n2,如果n2=m則找到了所要找的數(shù)據(jù)，否則繼續(xù)搜索；；-來看最后一個數(shù)據(jù)nn，如果nn=m則找到了要找的數(shù)據(jù)，否則打印沒有搜索到合適的數(shù)據(jù)。!順序搜索的模塊定義MODULESEARCH_MODULEIMPLICITNONE!接口說明INTERFACESequence_SearchMODULEPROCEDURESequence_Search_rMODULEPROCEDURESequence_Search_dMODULEPROCEDURESequence_Search_iENDINTERFACECONTAINS!實數(shù)的順序搜索LOGICALFUNCTIONSequence_Search_r(A,G)IMPLICITNONE!變量定義REAL::A(:),GINTEGER::N,I!搜索數(shù)據(jù)N=SIZE(A)DOI=1,NIF(G==A(I))THENSequence_Search_r=.TRUE.RETURNENDIFENDDOSequence_Search_r=.FALSE.RETURNENDFUNCTIONSequence_Search_r!雙精度數(shù)的順序搜索LOGICALFUNCTIONSequence_Search_d(A,G)IMPLICITNONE!變量定義REAL(8)::A(:),GINTEGER::N,I!搜索數(shù)據(jù)N=SIZE(A)DOI=1,NIF(G==A(I))THENSequence_Search_d=.TRUE.RETURNENDIFENDDOSequence_Search_d=.FALSE.RETURNENDFUNCTIONSequence_Search_d!整數(shù)的順序搜索LOGICALFUNCTIONSequence_Search_i(A,G)IMPLICITNONE!變量定義INTEGER::A(:),GINTEGER::N,I!搜索數(shù)據(jù)N=SIZE(A)DOI=1,NIF(G==A(I))THENSequence_Search_i=.TRUE.RETURNENDIFENDDOSequence_Search_i=.FALSE.RETURNENDFUNCTIONSequence_Search_iENDMODULESEARCH_MODULE!順序搜索范例，調(diào)用以上模塊的主程序PROGRAMTEST1601USESEARCH_MODULEIMPLICITNONE!變量定義INTEGER,ALLOCATABLE::I4(:)REAL,ALLOCATABLE::R4(:)REAL(8),ALLOCATABLE::R8(:)REAL::TempINTEGER::IgREAL::RgREAL(8)::DgINTEGER::N,Type,Err,I!初始化PRINT*,'請輸入隨機數(shù)數(shù)量:’READ(*,*)NPRINT*,'請選擇數(shù)據(jù)類型［1-整型2-實型3-雙精度］'READ(*,*)TypePRINT*,'請輸入要查找的數(shù)據(jù)’CALLRANDOM_SEED()!不同的搜索方法SELECTCASE(Type)CASE(1)ALLOCATE(I4(N),STAT=Err)IF(0/=Err)THENPRINT*,'內(nèi)存分配失敗!’STOPENDIFDOI=1,NCALLRANDOM_NUMBER(Temp)I4(I)=ANINT(Temp*6.0)ENDDOREAD(*,*)IgPRINT*,'原始數(shù)據(jù)序列:’，I4IF(Sequence_Search(I4,Ig))THENPRINT*,'數(shù)據(jù)序列中存在數(shù)據(jù):’，IgELSEPRINT*,'沒有要查找的數(shù)據(jù)!’ENDIFCASE(2)ALLOCATE(R4(N),STAT=Err)IF(0/=Err)THENPRINT*,'內(nèi)存分配失敗!’STOPENDIFCALLRANDOM_NUMBER(R4)READ(*,*)RgPRINT*,'原始數(shù)據(jù)序列:’，R4IF(Sequence_Search(R4,Rg))THENPRINT*,'數(shù)據(jù)序列中存在數(shù)據(jù):’，RgELSEPRINT*,'沒有要查找的數(shù)據(jù)!’ENDIFCASE(3)ALLOCATE(R8(N),STAT=Err)IF(0/=Err)THENPRINT*,'內(nèi)存分配失敗!’STOPENDIFCALLRANDOM_NUMBER(R8)READ(*,*)DgPRINT*,'原始數(shù)據(jù)序列:’，R8IF(Sequence_Search(R8,Dg))THENPRINT*,'數(shù)據(jù)序列中存在數(shù)據(jù):’，DgELSEPRINT*,'沒有要查找的數(shù)據(jù)!’ENDIFENDSELECTENDPROGRAMTEST1601二分搜索-順序搜索思路簡單，但效率不高。二分法是一種常見的高效、通用的搜索算法，但是必須配合排序好的數(shù)據(jù)才能正常的使用。如果將要搜索的數(shù)據(jù)使用數(shù)組進行保存并按照從小到大的順序進行排列，則二分法的基本步驟如下：-取數(shù)組的中間值M與要搜索的數(shù)據(jù)G對比，如果M=G則完成了搜索。如果M>G，在數(shù)據(jù)進行了排序的情況下，則要搜索的數(shù)據(jù)G一定在數(shù)組的下半部分；如果M<G，則要搜索的數(shù)據(jù)G一定在數(shù)組的上半部分。-根據(jù)數(shù)據(jù)G在數(shù)組中的位置來重新分組，重復(fù)執(zhí)行前一步繼續(xù)進行尋找。如果重新分組已經(jīng)執(zhí)行到不能再繼續(xù)下去，此時還沒有找到要搜索的數(shù)據(jù)G，則表示在搜索的數(shù)據(jù)中不存在要尋找的數(shù)據(jù)。!二分搜索的模塊定義MODULESearch_ModuleIMPLICITNONE!接口說明INTERFACEBinary_SearchMODULEPROCEDUREBinary_Search_iMODULEPROCEDUREBinary_Search_rMODULEPROCEDUREBinary_Search_dENDINTERFACEBinary_searchCONTAINS!整數(shù)的二分搜索LOGICALFUNCTIONBinary_Search_i(S,G)IMPLICITNONE!變量定義INTEGER::S(:),GINTEGER::N,L,R,M!輸入數(shù)據(jù)信息N=SIZE(S)L=1R=NM=(L+R)/2IF((G<S(1)).OR.(G>S(N)))THENBinary_Search_i=.FALSE.RETURNENDIF!二分搜索DOWHILE(L<R)IF(G>S(M))THENL=M+1M=(L+R)/2ELSEIF(G<S(M))THENR=M-1M=(L+R)/2ELSEBinary_Search_i=.TRUE.RETURNENDIFENDDOBinary_Search_i=.FALSE.RETURNENDFUNCTIONBinary_Search_i!實數(shù)的二分搜索LOGICALFUNCTIONBinary_Search_r(S,G)IMPLICITNONE!變量定義REAL::S(:),GINTEGER::N,L,R,M!輸入數(shù)據(jù)的信息N=SIZE(S)L=1R=NM=(L+R)/2IF((G<S(1)).OR.(G>S(N)))THENBinary_Search_r=.FALSE.RETURNENDIF!二分搜索DOWHILE(L<R)IF(G>S(M))THENL=M+1M=(L+R)/2ELSEIF(G<S(M))THENR=M-1M=(L+R)/2ELSEBinary_Search_r=.TRUE.RETURNENDIFENDDOBinary_Search_r=.FALSE.RETURNENDFUNCTIONBinary_Search_r!雙精度數(shù)的二分搜索LOGICALFUNCTIONBinary_Search_d(S,G)IMPLICITNONE!變量定義REAL(8)::S(:),GINTEGER::N,L,R,M!輸入數(shù)據(jù)的信息N=SIZE(S)L=1R=NM=(L+R)/2IF((G<S(1)).OR.(G>S(N)))THENBinary_Search_d=.FALSE.RETURNENDIF!二分搜索DOWHILE(L<R)IF(G>S(M))THENL=M+1M=(L+R)/2ELSEIF(G<S(M))THENR=M-1M=(L+R)/2ELSEBinary_Search_d=.TRUE.RETURNENDIFENDDOBinary_Search_d=.FALSE.RETURNENDFUNCTIONBinary_Search_dENDMODULESearch_Module!二分法主程序PROGRAMTEST1602USESEARCH_MODULEIMPLICITNONE!變量定義INTEGER::I4(10)=(/1,3,5,6,9,10,13,20,25,34/)INTEGER::Ig!搜索并顯示PRINT*,'請輸入要查找的數(shù)據(jù)’READ(*,*)IgPRINT*,'原始數(shù)據(jù)序列:’，I4IF(Binary_Search(I4,Ig))THENPRINT*,'數(shù)據(jù)序列中存在數(shù)據(jù):’，IgELSEPRINT*,'沒有要查找的數(shù)據(jù)!’ENDIFENDPROGRAMTEST1602散列搜索-散列搜索是一種相當(dāng)高效的搜索算法，在使用恰當(dāng)?shù)那闆r下，幾乎只需要做一次對比操作就能判斷某一個數(shù)據(jù)是否在一組目標(biāo)數(shù)據(jù)中。-散列搜索的主要精力放在了如何將數(shù)據(jù)放置在內(nèi)存中。當(dāng)數(shù)據(jù)在內(nèi)存中排列好之后，搜索數(shù)據(jù)只需要計算它可能出現(xiàn)在內(nèi)存中的具體位置并與該位置的實際數(shù)據(jù)進行對比即可。散列搜索沒有現(xiàn)成的計算公式可供使用，基本的思想就是一個內(nèi)存位置對應(yīng)一個具體數(shù)據(jù)，并且兩者之間存在某種聯(lián)系。!散列搜索范例PROGRAMTEST1603IMPLICITNONE!變量定義INTEGER::S(10)=(/1,3,8,4,56,100,200,12,34,67/)INTEGER::A(200)INTEGER::G,I!提示輸出PRINT*,'請輸入要查找的數(shù)據(jù):’READ(*,*)GIF((G<0).OR.(G>200))THENPRINT*,'要查找的數(shù)據(jù)不在搜索范圍內(nèi)!’STOPENDIF!初始化A=0DOI=1,10A(S(I))=IENDDO!散列搜蘇IF(A(G)/=0)THENPRINT*,'數(shù)據(jù)中存在要搜索的結(jié)果:’，GPRINT*,'位于：'，A(G)ELSEPRINT*,'沒有搜索到數(shù)據(jù)!'ENDIFENDPROGRAMTEST16034.冒泡法-冒泡法是最簡單的一種排序方法。盡管該方法的思想較為簡單，但實際的排序效率較低。如果有N個數(shù)據(jù)需要進行排序，則需要對數(shù)據(jù)作N-1次掃描工作。-冒泡法的基本步驟如下：-從第一個數(shù)字開始，依次比較相鄰兩個數(shù)據(jù)的大小。如果第一個數(shù)比第二個數(shù)大，則交換兩者的位置；-重復(fù)上述工作，直到倒數(shù)第二個數(shù)據(jù)；-從第一步開始，重新進行新的掃描。-在上面的算法中，由于每次掃描都將剩余數(shù)據(jù)中的最大值放到了最后邊，因此每次掃描的數(shù)據(jù)會越來越少，最后形成的新數(shù)據(jù)排列是按從小到大的方式進行的。這就好像水里的氣泡，越輕的越在上面。當(dāng)然，上面的排序結(jié)果也可以反過來，從大到小進行排列也是可以的。!冒泡排序模塊MODULESORT_MODULEIMPLICITNONE!接口說明INTERFACEBubble_SortMODULEPROCEDUREBubble_Sort_rMODULEPROCEDUREBubble_Sort_iMODULEPROCEDUREBubble_Sort_dENDINTERFACECONTAINS!實數(shù)冒泡排序SUBROUTINEBubble_Sort_r(A)IMPLICITNONE!變量定義REAL：：A(：)INTEGER::N,I,JREAL::Temp!排序N=SIZE(A)DOJ=N-1,1,-1DOI=1,JIF(A(I)>A(I+1))THENTemp=A(I)A(I)=A(I+1)A(I+1)=TempENDIFENDDOENDDOENDSUBROUTINE!整數(shù)冒泡排序SUBROUTINEBubble_Sort_i(A)IMPLICITNONE!變量定義INTEGER::A(:)INTEGER::N,I,JINTEGER::Temp!排序N=SIZE(A)DOJ=N-1,1,-1DOI=1,JIF(A(I)>A(I+1))THENTemp=A(I)A(I)=A(I+1)A(I+1)=TempENDIFENDDOENDDOENDSUBROUTINE!雙精度數(shù)排序SUBROUTINEBubble_Sort_d(A)IMPLICITNONE!變量定義REAL(8)::A(:)INTEGER::N,I,JREAL(8)::Temp!排序N=SIZE(A)DOJ=N-1,1,-1DOI=1,JIF(A(I)>A(I+1))THENTemp=A(I)A(I)=A(I+1)A(I+1)=TempENDIFENDDOENDDOENDSUBROUTINEENDMODULESORT_MODULE!冒泡排序PROGRAMTEST1605USESORT_MODULEIMPLICITNONE!變量定義INTEGER,ALLOCATABLE::I4(:)REAL,ALLOCATABLE::R4(:),TempREAL(8),ALLOCATABLE::R8(:)INTEGER::N,Type,Err,I!提示信息PRINT*,'請輸入隨機數(shù)數(shù)量:’READ(*,*)NPRINT*,'請選擇數(shù)據(jù)類型［1-整型2-實型3-雙精度］'READ(*,*)TypeCALLRANDOM_SEED()!開始排序SELECTCASE(Type)CASE(1)ALLOCATE(I4(N),STAT=Err)IF(0/=Err)THENPRINT*,'內(nèi)存分配失敗!’STOPENDIFDOI=1,NCALLRANDOM_NUMBER(Temp)I4(I)=ANINT(Temp*5.0)ENDDOPRINT*,'原始數(shù)據(jù)序列:’，I4CALLBubble_Sort(I4)PRINT*,'排序后數(shù)據(jù)序列:’，I4CASE(2)ALLOCATE(R4(N),STAT=Err)IF(0/=Err)THENPRINT*,'內(nèi)存分配失敗!’STOPENDIFCALLRANDOM_NUMBER(R4)PRINT*,'原始數(shù)據(jù)序列:’，R4CALLBubble_Sort(R4)PRINT*,'排序后數(shù)據(jù)序列:’，R4CASE(3)ALLOCATE(R8(N),STAT=Err)IF(0/=Err)THENPRINT*,'內(nèi)存分配失敗!’STOPENDIFCALLRANDOM_NUMBER(R8)PRINT*,'原始數(shù)據(jù)序列:’，R8CALLBubble_Sort(R8)PRINT*,'排序后數(shù)據(jù)序列:’，R8ENDSELECTENDPROGRAMTEST16055.選擇排序法-選擇排序法在某種形式上與冒泡法較為相似，冒泡法如果找到兩個數(shù)中較大的一個就將其放到第二個數(shù)字的位置；而選擇排序法則會將一組數(shù)據(jù)中的第一個數(shù)字與其后所有的數(shù)據(jù)進行比較，如果這個數(shù)字較小則將其放置于這組數(shù)據(jù)的第一個位置上。-對于一個有N個數(shù)字的一組數(shù)組，選擇排序法的基本步驟如下：-找出N個數(shù)據(jù)中最大或最小的一個，并將其與這組數(shù)據(jù)中的第一個數(shù)字交換位置；-找出剩余N-1個數(shù)據(jù)中最大或最小的一個，并將其與這組數(shù)據(jù)中的第二個數(shù)字交換位置；-找出剩余N-2個數(shù)據(jù)中最大或最小的一個，并將其與這組數(shù)據(jù)中的第三個數(shù)字交換位置；；-找出最后兩個數(shù)據(jù)中最大或最小的一個，并將其與這組數(shù)據(jù)中倒數(shù)第二個數(shù)字交換位置。!選擇排序模塊MODULESORT_MODULEIMPLICITNONE!接口說明INTERFACESelect_SortMODULEPROCEDURESelect_Sort_rMODULEPROCEDURESelect_Sort_iMODULEPROCEDURESelect_Sort_dENDINTERFACECONTAINS!實數(shù)選擇排序SUBROUTINESelect_Sort_r(A)IMPLICITNONE!變量定義REAL::A(:)INTEGER::N,I,JREAL::Min,Temp!排序N=SIZE(A)DOJ=1,N-1Min=A(J)DOI=J+1,NIF(Min>A(I))THENTemp=A(J)A(J)=A(I)A(I)=TempMin=A(I)ENDIFENDDOENDDOENDSUBROUTINE!整數(shù)選擇排序SUBROUTINESelect_Sort_i(A)IMPLICITNONE!變量定義INTEGER::A(:)INTEGER::N,I,JINTEGER::Min,Temp!排序N=SIZE(A)DOJ=1,N-1Min=A(J)DOI=J+1,NIF(Min>A(I))THENTemp=A(J)A(J)=A(I)A(I)=TempMin=A(I)ENDIFENDDOENDDOENDSUBROUTINE!雙精度選擇排序SUBROUTINESelect_Sort_d(A)IMPLICITNONE!變量定義REAL(8)::A(:)INTEGER::N,I,JREAL(8)::Min,Temp!排序N=SIZE(A)DOJ=1,N-1Min=A(J)DOI=J+1,NIF(Min>A(I))THENTemp=A(J)A(J)=A(I)A(I)=TempMin=A(I)ENDIFENDDOENDDOENDSUBROUTINEENDMODULESORT_MODULE!選擇排序PROGRAMTEST1606USESORT_MODULEIMPLICITNONE!變量定義INTEGER,ALLOCATABLE::I4(:)REAL,ALLOCATABLE::R4(:)REAL(8),ALLOCATABLE::R8(:)INTEGER::N,Type,Err,IREAL::Temp!初始化PRINT*,'請輸入隨機數(shù)數(shù)量:’READ(*,*)NPRINT*,'請選擇數(shù)據(jù)類型［1-整型2-實型3-雙精度］'READ(*,*)TypeCALLRANDOM_SEED()!選擇排序方法進行排序SELECTCASE(Type)CASE(1)ALLOCATE(I4(N),STAT=Err)IF(0/=Err)THENPRINT*,'內(nèi)存分配失敗!’STOPENDIFDOI=1,NCALLRANDOM_NUMBER(Temp)I4(I)=ANINT(Temp*5.0)ENDDOPRINT*,'原始數(shù)據(jù)序列:’，I4CALLSelect_Sort(I4)PRINT*,'排序后數(shù)據(jù)序列:’，I4CASE(2)ALLOCATE(R4(N),STAT=Err)IF(0/=Err)THENPRINT*,'內(nèi)存分配失敗!’STOPENDIFCALLRANDOM_NUMBER(R4)PRINT*,'原始數(shù)據(jù)序列:’，R4CALLSelect_Sort(R4)PRINT*,'排序后數(shù)據(jù)序列:’，R4CASE(3)ALLOCATE(R8(N),STAT=Err)IF(0/=Err)THENPRINT*,'內(nèi)存分配失敗!’STOPENDIFCALLRANDOM_NUMBER(R8)PRINT*,'原始數(shù)據(jù)序列:’，R8CALLSelect_Sort(R8)PRINT*,'排序后數(shù)據(jù)序列:’，R8ENDSELECTENDPROGRAMTEST16066.4央速排序法-快速排序法名如其人，一般來說，快速排序法是目前最快的排序方法。對于一個有N個數(shù)據(jù)的序列而言，快速排序的基本步驟如下：-以序列中的第一個數(shù)字作為鍵值K，并令L=2、R=N；-以K為基準(zhǔn)，將小于K的數(shù)字往前移，大于K的數(shù)字往后移。移動完成后，自然會發(fā)現(xiàn)K在原始序列中的大小排名，這時將K放置于正確的位置上；-如果K的大小排名為M，則移動后的序列會分成大于K和小于K的兩組。此時，再將這兩組數(shù)字按上述方法繼續(xù)進行排序。-在快速排序法的第二步中，可以進一步詳細(xì)的進行說明：-從序列中的第二個數(shù)字開始，依次拿下一個數(shù)字與鍵值K比較，直到找到大于等于K的數(shù)值L為止。此時，將L重新設(shè)置為數(shù)值L在序列中的位置；-從序列中的倒數(shù)第二個數(shù)字開始，依次拿錢一個數(shù)字與鍵值K比較，直到找到小于等于K的數(shù)值M為止。此時，將N重新設(shè)置為數(shù)值M在序列中的位置；-如果L小于R，則把序列中L和R這兩個位置的數(shù)據(jù)交換，再回到上一步繼續(xù)執(zhí)行;如果L大于R，則將序列中的第一個數(shù)字與第R個數(shù)字互相交換。!快速排序模塊MODULESORT_MODULEIMPLICITNONE!接口說明INTERFACEFast_SortMODULEPROCEDUREFast_Sort_iMODULEPROCEDUREFast_Sort_rMODULEPROCEDUREFast_Sort_dENDINTERFACECONTAINS!實數(shù)排序SUBROUTINEFast_Sort_r(A,S,E)IMPLICITNONE!變量定義REAL::A(:)INTEGER::S,EINTEGER::N,L,R,KINTEGER::Temp!排序L=SR=E+1IF(R>=L)THENK=A(S)DODOL=L+1IF((A(L)>K).OR.(L>=E))EXITENDDODOR=R-1IF((A(R)<K).OR.(R<=E))EXITENDDOIF(R<=L)EXITTemp=A(R)A(R)=A(L)A(L)=TempENDDOTemp=A(S)A(S)=A(R)A(R)=TempCALLFast_Sort_r(A,S,R-1)CALLFast_Sort_r(A,R+1,E)ENDIFENDSUBROUTINEFast_Sort_r!整數(shù)排序SUBROUTINEFast_Sort_i(A,S,E)IMPLICITNONE變量定義INTEGER:A(:)INTEGER:S,EINTEGER:N,L,R,KINTEGER:Temp!排序L=SR=E+1IF(R>=L)THENK=A(S)DODOL=L+1IF((A(L)>K).OR.(L>=E))EXITENDDODOR=R-1IF((A(R)<K).OR.(R<=E))EXITENDDOIF(R<=L)EXITTemp=A(R)A(R)=A(L)A(L)=TempENDDOTemp=A(S)A(S)=A(R)A(R)=TempCALLFast_Sort_i(A,S,R-1)CALLFast_Sort_i(A,R+1,E)ENDIFENDSUBROUTINEFast_Sort_i!雙精度數(shù)排序SUBROUTINEFast_Sort_d(A,S,E)IMPL