演算法的應用 - 7

排序的方法有很多種，其中以泡沫排序法最為簡易學。

所謂泡沫排序(bubble sort) 是將兩相鄰的資料相互做比較，若比較發現次序不對，則將兩資料互換，依次由上往下比，而結果 ... 演算法的應用 在排序上的應用 由於陣列的使用，使原本複雜的程式得以簡化；因此，陣列的使用相當廣泛且重要。

本節將以資料處理中的運算、排序及搜尋來介紹，如何運用陣列來解決問題，同時複習前面所學習過的指述。

所謂排序(sorting)就是將一組資料依需要予以重新安排其順序。

排列的方式有兩種，一種是由小至大的遞增排序，另一種是由大至小的遞減排序。

依據資料的不同，排序意義也有不同，例如： 數值資料：依數字大小排序。

英文字：依字母的ASCII碼大小排列。

中文字：依字的筆畫多少排列。

泡沫排序法 排序的方法有很多種，其中以泡沫排序法最為簡易學。

所謂泡沫排序(bubblesort) 是將兩相鄰的資料相互做比較，若比較發現次序不對，則將兩資料互換，依次由上往下比，而結果則會依次由下往上浮起，猶如泡沫一般。

下列為一將五個數值資料 (3，4，6，8，9)由大至小做泡沫順序的情形。

以VB來表示的演算法如下： SubBubSort(ByRefA,n) 　ForI=1ton-1 　　Forj=I+1ton 　　　IfA(j)>A(I)then 　　　　Temp=A(I) 　　　　A(I)=A(j) 　　　　A(j)=Temp 　　　EndIf 　　Nextj 　NextI EndSub 效能分析： 一般而言，泡沫排序法至少必須比較1+2+3+……+n-1=n(n-1)/2次，其時間複雜度為O(n2)。

泡沫排序法並不須額外佔用太多的記憶體，僅須一個交換時暫存的變數，因此較不浪費記憶體。

通常泡沫排序法應用於較小的資料量，其效果較好。

　 選擇排序法 在泡沫排序中，每找到一個比目前變數大或小的數字時，就必須執行資料的交換，這樣的方法容易將時間浪費在資料的交換上，因此我們可採用改良的方式，在找到比目前大或小的數字時，先記錄其位置或索引值，待確定後再進行資料的交換，而這樣的方法我們稱之為選擇排序法，其動作模式如下：  以VB來表示的演算法如下： SubSel_Sort(ByRefA,n) 　ForI=1ton-1 　　NP=I 　　Forj=I+1ton 　　　IfA(j)>A(NP)thenNP=j 　　Nextj 　　Temp=A(I) 　　A(I)=A(NP) 　　A(NP)=Temp 　NextI EndSub 效能分析： 選擇排序法因資料變化不定，因此屬於不穩定的排序法。

其時間複雜度為O(n2)，且只需要兩個變數的額外空間，並不會浪費太多記憶體。

資料量愈小，其效果愈好。

快速排序法 在快速排序法中，通常必須要使用到遞迴的方法，其步驟分析如下： 假設目前陣列A的索引值為1到10共10個元素，則變數f=1、e=10，並設定i=f+1，j=e。

由陣列初始處往末尾處遞增(i=i+1)，直到A(i)>A(f)。

由陣列末尾處往初始處遞減(j=j-1)，直到A(j)=j則A(j)與A(f)交換，並以j為基準，將陣列分成左右兩陣列，分別重覆1~5的動作，直到f=e為止。

其行為模式如下所示。

以VB來表示的演算法如下： SubQuickSort(ByRefA,f,e) 　IffA(f)Andj>f:j=j-1:Wend 　　　IfiA(j)Then 　　　　temp=A(I):A(I)=A(j):A(j)=temp 　　　EndIf 　　Nextj 　NextI 　Rem=====print===== 　Print"由小至大排序後:"; 　ForI=1To5 　　PrintFormat(A(I),"00"); 　NextI EndSub 執行結果： 　 在搜尋上的應用 所謂搜尋(Search)就是在一群資料中找尋所要的特定資料；一般常用的搜尋方法有循序搜尋及二分搜尋兩種，敘述於下： 循序搜尋(sequentialsearch) 從資料的第一個開始依序一個個取出和"目的資料"相比較，直到找出所要的元素或所有資料均巳找完為止，這種搜尋法稱為循序搜尋。

此法是最簡單的搜尋方法，但速度也最慢。

二分搜尋(binarysearch) 二分搜尋改進了循序搜尋之速度慢的缺點，其作法如下： j首先將所有資料由小至大排序。

k設L(low)表最低項項數，H(high)表最高次數。

lM(middle)表中間項數＝INT(L＋H)／2 m將"目的資料"和中間項的資料做比較。

當目的資料＞中間項資料，則L＝M＋1。

當目的資料＜中間項資料，則H＝M－1。

當目的資料＝中間項資料，則表示巳找到。

n重定M，重覆步驟l和m，直到找到或所有資料均找過為止。

效能分析： 二分搜尋法在使用前，檔案或陣列必須是已排序。

其時間複雜度為O(log2n)，當資料量愈大，其效能愈好。

例7.5-2以循序搜尋法在下列資料中，找出任一資料，若找到則印出其為第n個資料，並計算其找尋次數；若找不印出"datsnotfound"。

程式碼： OptionExplicit Dima(10),b,i,kAsInteger PrivateSubcmdRnd_Click() 　Rem====產生整數亂數==== 　Cls 　Print"原始資料:"; 　Fori=1To10 　　a(i)=Int(Rnd*100)+1 　　PrintFormat(a(i),"00"); 　Nexti EndSub PrivateSubcmdSeq_Click() 　k=Val(InputBox("請輸入待搜尋資料---")) 　b=0 　Print:Print 　Print"循序搜尋==" 　Fori=1To10 　　Ifk=a(i)Then 　　　Print"共搜尋了"&i&"次，"&k;"在亂數數列中的第"&i&"個" 　　　b=1 　　　ExitFor 　　EndIf 　Nexti 　 　Ifb=0ThenPrint"找不到"&k EndSub PrivateSubcmdBin_Click() 　Diml,h,j,t,m,tmpAsInteger 　Rem===進行排序=== 　Fori=1To9 　　Forj=i+1To10 　　　Ifa(i)>a(j)Thentmp=a(i):a(i)=a(j):a(j)=tmp 　　Nextj 　Nexti 　Print:Print 　Print"排序後數列："; 　Fori=1To10 　　Printa(i); 　Nexti ' 　Rem===進行二分搜尋=== 　k=Val(InputBox("請輸入待搜尋資料---")) 　Print:Print 　Print"二分搜尋==" 　l=1:h=10:t=0 　DoWhilel<=h 　　m=Int((l+h)/2):t=t+1 　　Ifk=a(m)Then 　　　Print"一共找了"&t&"次，"&k;"在排序後的第"&m&"個" 　　　ExitDo 　　EndIf 　　Ifka(m)ThenPrint"找不到"&k EndSub 執行結果： 輸入資料：71、54、58、29、31、78、02、77、82、71 程式說明：