首頁 > 學院 > 邏輯算法 > 正文

排序算法

2020-10-03 20:14:49
字體:
來源:轉載
供稿:網友

為什么有這么多的排序算法?

首先,在計算機編程中排序是一個經常遇到的問題。數據只有經過排序后,才更有意義。其次,排序算法說明了許多重要的算法的技術,例如二進制細分,遞歸和線性添加。最后要說明的一點是不同的算法有不同的優缺點,沒有一種算法在任何情況下都是最好的算法。

汽泡排序法

該算法是專門針對已部分排序的數據進行排序的一種排序算法。如果在你的數據清單中只有一兩個數據是亂序的話,用這種算法就是最快的排序算法。如果你的數據清單中的數據是隨機排列的,那么這種方法就成了最慢的算法了。因此在使用這種算法之前一定要慎重。

這種算法的核心思想是掃描數據清單,尋找出現亂序的兩個相鄰的項目。當找到這兩個項目后,交換項目的位置然后繼續掃描。重復上面的操作直到所有的項目都按順序排好。

圖1是對這種算法的說明。在該例中,數字1的未按順序排好。第一次掃描清單時,程序找到4和1是兩個相鄰的亂序項目,于是交換它們的位置。以此類推,直到將所有的項目按1234排好。數字1就象上升的汽泡一樣,這就是這一算法名稱的由來。

2221
3312
4133
1444
圖1.

你可以改進該算法,讓程序自下而上開始掃描,這樣只須一次就能排好順序了。

下面是用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

計數排序法

前面提到過,對于使用比較法作為算法基礎的算法來說,最快需N * log(N)步才能完成排序。計數排序法不作用比較,所以它不受此限制。實際上該算法是如此之快,以致于你會認為是使用了魔術,而不是數學運算來排序。

另一方面,計數排序法只能用于特殊的情況。首先,所有的要進行排序的數據必須是整數,不能對字符使用該算法;其次,數據的范圍有限,如果你的數據是在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

總結

下表是各種算法的優缺點比較,正如你所見到的那樣,每種算法只是在某一情況下表現得最好,下面是選擇算法時的一些原則:

  • 如果你的數據列表中有99%數據已排過序,則用汽泡排序法。
  • 如果你要排序的數據較少(100個以下),則用選擇排序法。
  • 如果你的數據都是整數,并且數值不大(幾千以內),則用計數排序法。
  • 否則的話用快速排序法法
算法優點缺點
汽泡排序法對以初步排序的數據來說這種方法的速度很快在其它情況下運行速度較慢
選擇排序法非常簡單對大量數據的排序速度很慢
容易明白
對于少量數據的排序來說速度很快
快速排序法對大量數據的排序來說速度很快如果有大量重復的數據就比較麻煩
計數排序法當數據數值較小(1-1000之間)時,速度非???/TD>當數據數值較大時,速度較慢
需額外的內存
只能對整數類型的數據排序
上一篇:linux loadavg 算法

下一篇:返回列表

發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表

圖片精選

金玫玫床戏