排序演算法

  想想看,如果我們的電話簿不是依照姓名的筆劃數排列,而是雜亂無章隨便編排的話,當我們要尋找某個人的姓名時,是不是就要花費較多的時間,因此,當我們想要在大量的資料中尋找某一筆資料時,我們會把這些資料先做排序,而後再依據排序的規則來做搜尋,如電話簿即是一例,它就依姓名筆劃來排序,因此我們想找尋某一人電話時,只要算一算筆劃,很快地,就可以找到這個人的電話了。

例:有一陣列A存放的資料為〔27,7,2,9,4,85〕,試將此陣列由小而大排列。

交換排序法(exchange sort) 選擇排序法(selection sort) 插入排序法(insertion sort)
合併排序法(merge sort)  快速排序法(Quick sort)  演算法的比較         

交換排序法(exchange sort)

說明:

(1)拿第一個數與其他數做比較,只要數字比第一個小,則兩數交換,那麼,當全部的數都比過之後,最小數即找出,且放在第一個位置。

(2)重覆(1)的步驟,但由第2個開始比較起,直至此陣列達到已排序狀態。

(3)交換的次數較多。

(4)適用於未排序的狀況。

輸入:n個資料的陣列A

輸出:A陣列中的資料依一定的次序排列

演算法:

 private Sub Form_Activate()

 Dim A(n) As Integer

 Dim n As Integer

 Dim I As Integer

 Dim J As Integer

 For I = 1 to n-1

 For J:=1 to n

 If A[J] < A[I] then

 Change A[I] and A[J]

 End If

 Next J

 Next I

 End Sub

圖解:

top

選擇排序法(selection sort)

說明:

(1)在此陣列中搜尋出最小的,放在第一個位置,第二小的放在第二個位置,直至全部都排列完成。

(2)交換的次數較少。

輸入:n個資料的陣列A

輸出:A陣列中的資料依一定的次序排列

演算法:

 private Sub Form_Activate()

 Dim A(n) As Integer

 Dim n As Integer

 Dim I As Integer

 Dim J As Integer

 Dim smallest Integer

 For I = 1 to n-1

 Smallest = I

 For J:=I + 1 to n

 If A[J] < A[smallest] then

 Smallest = J

 End If

 Next J

 change A[I] and A[smallest]

 Next I

 End Sub

實例:

top

插入排序法(insertion sort)

說明:它的用途是將數字插入已排序的數列中。

輸入:n個資料的陣列A

輸出:A陣列中的資料依一定的次序排列

演算法:

 private Sub Form_Activate()

 Dim A(n) As Integer

 Dim n As Integer

 Dim I As Integer

 Dim J As Integer

 Dim x As Integer

 For I = 2 to n

 x = A[I]

 J = I - 1

 Do While J > 0 and A[j] > x

 A[J+1] = A[j]

 J = J - 1

 Loop

 A[l+1] = x

 Next I

 End Sub

圖解:

top

合併排序法(merge sort)

說明:

(1)將數列分成(divide)兩個子數列,每一個數列擁有n/2個數字。

(2)排列每一個子數列,除非此子數列夠小(只剩一個數字),否則再繼續重覆(1)。

(3)結合(merge)每一個子數列使之成為單一數列。

輸入:n個資料的陣列A

輸出:A陣列中的資料依一定的次序排列

演算法:

 private Sub MergeSort()

 Dim A(n) As Integer

 Dim n As Integer

 Const h = n \ 2

 Const m = n - h

 Dim X(h) As Integer

 Dim Y(m) As Integer

 If n > 1 then

 Copy A[I] through A[h] to X

 Copy A[h+I] through A[n] to Y

 Mergesort(h,X)

 Mergesort(m,Y)

 Merge(h,m,X,Y,A)

 End If

 End Sub

圖解:

top

快速排序法(Quick sort)

說明:

(1)先找一個指標(為求方便,通常是第一個數),將,數列中大於這個指標的數,都放在右邊,反之則放在左邊。

(2)和合併排序法相似,但快速排序法的優點是比較節省空間。

輸入:n個資料的陣列A

輸出:A陣列中的資料依一定的次序排列

演算法:

 private Sub Quick_Sort()

 Dim A(n) As Integer

 Dim n As Integer

 Dim high As Integer

 Dim low As Integer

 Dim pivot As Integer

 If high > low then

 Partition(low,high,pivot)

 Quick_Sort(low,pivot-1)

 Quick_Sort(piovt+1,high)

 End If

 End Sub

實例:

top

演算法的比較

排序法名稱

優點

缺點

Exchange

 

交換次數很多

Insertion

適用於數列較小的情況

最耗時間

Merge

運作的時間最快

須要額外的空間來處理

Quick

運作的時間最快

須要額外空間來處理,但沒有Merge Sort須要的空間多。

觀賞時請按滑鼠左鍵,可單獨觀賞或連續按下

 氣泡排序法
  (Bubble Sort) 

雙向氣泡排序法
(Bi-Directional Bubble Sort)

快速排序法
(Quick Sort)

 

  演算法並沒有所謂的好與壞,而是視你要解決的問題來選擇較適用的演算法,且各種演算法可搭配使用,亦可自己想出一套更快更有效率的演算法。

top