首先，在計算機編程中排序是一個經常遇到的問題。數據只有經過排序后，才更有意義。其次，排序算法說明了許多重要的算法的技術，例如二進制細分，遞歸和線性添加。最后要說明的一點是不同的算法有不同的優缺點，沒有一種算法在任何情況下都是最好的算法。
這種算法的核心思想是掃描數據清單，尋找出現亂序的兩個相鄰的項目。當找到這兩個項目后，交換項目的位置然后繼續掃描。重復上面的操作直到所有的項目都按順序排好。
圖1是對這種算法的說明。在該例中，數字1的未按順序排好。第一次掃描清單時，程序找到4和1是兩個相鄰的亂序項目，于是交換它們的位置。以此類推，直到將所有的項目按1234排好。數字1就象上升的汽泡一樣，這就是這一算法名稱的由來。
| 2 | 2 | 2 | 1 |
| 3 | 3 | 1 | 2 |
| 4 | 1 | 3 | 3 |
| 1 | 4 | 4 | 4 |
你可以改進該算法，讓程序自下而上開始掃描，這樣只須一次就能排好順序了。
下面是用VB代碼實現這一算法的例子：
' min and max are the minimum and maximum indexes' of the items that might still be out of order.Sub BubbleSort (List() As Long, ByVal min As Integer, _ ByVal max As Integer)Dim last_swap As IntegerDim i As IntegerDim j As IntegerDim tmp As Long ' Repeat until we are done. Do While min < max ' Bubble up. last_swap = min - 1 ' For i = min + 1 To max i = min + 1 Do While i <= max ' Find a bubble. If List(i - 1) > List(i) Then ' See where to drop the bubble. tmp = List(i - 1) j = i Do List(j - 1) = List(j) j = j + 1 If j > max Then Exit Do Loop While List(j) < tmp List(j - 1) = tmp last_swap = j - 1 i = j + 1 Else i = i + 1 End If Loop ' Update max. max = last_swap - 1 ' Bubble down. last_swap = max + 1 ' For i = max - 1 To min Step -1 i = max - 1 Do While i >= min ' Find a bubble. If List(i + 1) < List(i) Then ' See where to drop the bubble. tmp = List(i + 1) j = i Do List(j + 1) = List(j) j = j - 1 If j < min Then Exit Do Loop While List(j) > tmp List(j + 1) = tmp last_swap = j + 1 i = j - 1 Else i = i - 1 End If Loop ' Update min. min = last_swap + 1 LoopEnd Sub |
選擇排序法 選擇排序法是一個很簡單的算法。其原理是首先找到數據清單中的最小的數據，然后將這個數據同第一個數據交換位置；接下來找第二小的數據，再將其同第二個數據交換位置，以此類推。下面是VB代碼實現該算法。
Sub Selectionsort (List() As Long, min As Integer, _ max As Integer)Dim i As IntegerDim j As IntegerDim best_value As LongDim best_j As Integer For i = min To max - 1 best_value = List(i) best_j = i For j = i + 1 To max If List(j) < best_value Then best_value = List(j) best_j = j End If Next j List(best_j) = List(i) List(i) = best_value Next iEnd Sub |
當尋找第I小的數據時，你必須檢查N-I個項目，所以這一算法所用的步驟可用下面這個公式求得。
N + (N - 1) + (N - 2) + ... + 1 = N * (N + 1) / 2
選擇排序法適用于較少數據的排序。此外由于算法較簡單，因此他的代碼也比較簡單，這就為我們維護代碼帶來了方便。實際上如果你的數據相當少的話，這種算法的速度快過其它更復雜的算法。
通常分割點的數據是隨機選取的。這樣無論你的數據是否已被排列過，你所分割成的兩個字列表的大小是差不多的。而只要兩個子列表的大小差不多，該算法所需的步驟就是N * log(N) 步。對于使用比較法進行排序的算法來講這是最快的方法。下面是用VB代碼實現這一算法的例子。
Sub Quicksort (List() As Long, min As Integer, max As Integer)Dim med_value As LongDim hi As IntegerDim lo As IntegerDim i As Integer ' If the list has no more than 1 element, it's sorted. If min >= max Then Exit Sub ' Pick a dividing item. i = Int((max - min + 1) * Rnd + min) med_value = List(i) ' Swap it to the front so we can find it easily. List(i) = List(min) ' Move the items smaller than this into the left ' half of the list. Move the others into the right. lo = min hi = max Do ' Look down from hi for a value < med_value. Do While List(hi) >= med_value hi = hi - 1 If hi <= lo Then Exit Do Loop If hi <= lo Then List(lo) = med_value Exit Do End If ' Swap the lo and hi values. List(lo) = List(hi) ' Look up from lo for a value >= med_value. lo = lo + 1 Do While List(lo) < med_value lo = lo + 1 If lo >= hi Then Exit Do Loop If lo >= hi Then lo = hi List(hi) = med_value Exit Do End If ' Swap the lo and hi values. List(hi) = List(lo) Loop ' Sort the two sublists Quicksort List(), min, lo - 1 Quicksort List(), lo + 1, maxEnd Sub |
另一方面，計數排序法只能用于特殊的情況。首先，所有的要進行排序的數據必須是整數，不能對字符使用該算法；其次，數據的范圍有限，如果你的數據是在1到1000之內，用這種算法的效果就非常好，但如果你的數據是在1到30000之間，該算法就根本不能用。
首先該算法創建一個整數類型的臨時數組，該數組的上下標分別是要排序的數據的最大最小值。如果數據列表的最大最小值從min_item到max_item, 該算法就將數組創建成下面這樣： Dim Counts() As Integer ReDim Counts(min_item To max_item)接下來，算法檢查列表中的每一個項目，并增加對應該項目的數組元素的值，當這一階段完成后，Counts(I)的數值就是就是數值為I的基礎上的個數。 For I = min To Max Counts(List(I)) = Counts(List(I)) + 1 Next I
程序掃描Counts數組，將counts轉換成被排序列表中的偏移量。 next_spot = 1 For i = min_value To max_value this_count = counts(i) counts(i) = next_spot next_spot = next_spot + this_count Next i
最后將數據進行排序
下面是實現該算法的VB代碼
Sub Countingsort (List() As Long, sorted_list() As Long, _ min As Integer, max As Integer, min_value As Long, _ max_value As Long)Dim counts() As IntegerDim i As IntegerDim this_count As IntegerDim next_offset As Integer ' Create the Counts array. ReDim counts(min_value To max_value) ' Count the items. For i = min To max counts(List(i)) = counts(List(i)) + 1 Next i ' Convert the counts into offsets. next_offset = min For i = min_value To max_value this_count = counts(i) counts(i) = next_offset next_offset = next_offset + this_count Next i ' Place the items in the sorted array. For i = min To max sorted_list(counts(List(i))) = List(i) counts(List(i)) = counts(List(i)) + 1 Next iEnd Sub |
| 算法 | 優點 | 缺點 |
|---|---|---|
| 汽泡排序法 | 對以初步排序的數據來說這種方法的速度很快 | 在其它情況下運行速度較慢 |
| 選擇排序法 | 非常簡單 | 對大量數據的排序速度很慢 |
| 容易明白 | ||
| 對于少量數據的排序來說速度很快 | ||
| 快速排序法 | 對大量數據的排序來說速度很快 | 如果有大量重復的數據就比較麻煩 |
| 計數排序法 | 當數據數值較小(1-1000之間)時，速度非?？?/TD> | 當數據數值較大時，速度較慢 |
| 需額外的內存 | ||
| 只能對整數類型的數據排序 |
新聞熱點
疑難解答
