首先，在計(jì)算機(jī)編程中排序是一個(gè)經(jīng)常遇到的問題。數(shù)據(jù)只有經(jīng)過排序后，才更有意義。其次，排序算法說明了許多重要的算法的技術(shù)，例如二進(jìn)制細(xì)分，遞歸和線性添加。最后要說明的一點(diǎn)是不同的算法有不同的優(yōu)缺點(diǎn)，沒有一種算法在任何情況下都是最好的算法。
這種算法的核心思想是掃描數(shù)據(jù)清單，尋找出現(xiàn)亂序的兩個(gè)相鄰的項(xiàng)目。當(dāng)找到這兩個(gè)項(xiàng)目后，交換項(xiàng)目的位置然后繼續(xù)掃描。重復(fù)上面的操作直到所有的項(xiàng)目都按順序排好。
圖1是對(duì)這種算法的說明。在該例中，數(shù)字1的未按順序排好。第一次掃描清單時(shí)，程序找到4和1是兩個(gè)相鄰的亂序項(xiàng)目，于是交換它們的位置。以此類推，直到將所有的項(xiàng)目按1234排好。數(shù)字1就象上升的汽泡一樣，這就是這一算法名稱的由來。
| 2 | 2 | 2 | 1 |
| 3 | 3 | 1 | 2 |
| 4 | 1 | 3 | 3 |
| 1 | 4 | 4 | 4 |
你可以改進(jìn)該算法，讓程序自下而上開始掃描，這樣只須一次就能排好順序了。
下面是用VB代碼實(shí)現(xiàn)這一算法的例子：
' 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 |
選擇排序法 選擇排序法是一個(gè)很簡(jiǎn)單的算法。其原理是首先找到數(shù)據(jù)清單中的最小的數(shù)據(jù)，然后將這個(gè)數(shù)據(jù)同第一個(gè)數(shù)據(jù)交換位置；接下來找第二小的數(shù)據(jù)，再將其同第二個(gè)數(shù)據(jù)交換位置，以此類推。下面是VB代碼實(shí)現(xiàn)該算法。
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 |
當(dāng)尋找第I小的數(shù)據(jù)時(shí)，你必須檢查N-I個(gè)項(xiàng)目，所以這一算法所用的步驟可用下面這個(gè)公式求得。
N + (N - 1) + (N - 2) + ... + 1 = N * (N + 1) / 2
選擇排序法適用于較少數(shù)據(jù)的排序。此外由于算法較簡(jiǎn)單，因此他的代碼也比較簡(jiǎn)單，這就為我們維護(hù)代碼帶來了方便。實(shí)際上如果你的數(shù)據(jù)相當(dāng)少的話，這種算法的速度快過其它更復(fù)雜的算法。
通常分割點(diǎn)的數(shù)據(jù)是隨機(jī)選取的。這樣無論你的數(shù)據(jù)是否已被排列過，你所分割成的兩個(gè)字列表的大小是差不多的。而只要兩個(gè)子列表的大小差不多，該算法所需的步驟就是N * log(N) 步。對(duì)于使用比較法進(jìn)行排序的算法來講這是最快的方法。下面是用VB代碼實(shí)現(xiàn)這一算法的例子。
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 |
另一方面，計(jì)數(shù)排序法只能用于特殊的情況。首先，所有的要進(jìn)行排序的數(shù)據(jù)必須是整數(shù)，不能對(duì)字符使用該算法；其次，數(shù)據(jù)的范圍有限，如果你的數(shù)據(jù)是在1到1000之內(nèi)，用這種算法的效果就非常好，但如果你的數(shù)據(jù)是在1到30000之間，該算法就根本不能用。
首先該算法創(chuàng)建一個(gè)整數(shù)類型的臨時(shí)數(shù)組，該數(shù)組的上下標(biāo)分別是要排序的數(shù)據(jù)的最大最小值。如果數(shù)據(jù)列表的最大最小值從min_item到max_item, 該算法就將數(shù)組創(chuàng)建成下面這樣： Dim Counts() As Integer ReDim Counts(min_item To max_item)接下來，算法檢查列表中的每一個(gè)項(xiàng)目，并增加對(duì)應(yīng)該項(xiàng)目的數(shù)組元素的值，當(dāng)這一階段完成后，Counts(I)的數(shù)值就是就是數(shù)值為I的基礎(chǔ)上的個(gè)數(shù)。 For I = min To Max Counts(List(I)) = Counts(List(I)) + 1 Next I
程序掃描Counts數(shù)組，將counts轉(zhuǎn)換成被排序列表中的偏移量。 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
最后將數(shù)據(jù)進(jìn)行排序
下面是實(shí)現(xiàn)該算法的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 |
| 算法 | 優(yōu)點(diǎn) | 缺點(diǎn) |
|---|---|---|
| 汽泡排序法 | 對(duì)以初步排序的數(shù)據(jù)來說這種方法的速度很快 | 在其它情況下運(yùn)行速度較慢 |
| 選擇排序法 | 非常簡(jiǎn)單 | 對(duì)大量數(shù)據(jù)的排序速度很慢 |
| 容易明白 | ||
| 對(duì)于少量數(shù)據(jù)的排序來說速度很快 | ||
| 快速排序法 | 對(duì)大量數(shù)據(jù)的排序來說速度很快 | 如果有大量重復(fù)的數(shù)據(jù)就比較麻煩 |
| 計(jì)數(shù)排序法 | 當(dāng)數(shù)據(jù)數(shù)值較小(1-1000之間)時(shí)，速度非?？?/TD> | 當(dāng)數(shù)據(jù)數(shù)值較大時(shí)，速度較慢 |
| 需額外的內(nèi)存 | ||
| 只能對(duì)整數(shù)類型的數(shù)據(jù)排序 |
新聞熱點(diǎn)
疑難解答
圖片精選
