基於Go語言實現冒泡排序算法

Posted on by

冒泡排序

冒泡排序是交換排序中最簡單的一種算法。 算法思路：

  • 遍歷數組，相鄰的兩個元素進行比較，以升序為例，如果前面的元素大於後面的元素，則將它們的位置進行交換
  • 第一輪遍歷結束之後，最大的元素會處於所遍歷范圍的最後一個位置，然後繼續下一輪遍歷
  • 每輪都會固定一個元素，直到所有元素都被固定，因此會執行 n – 1輪，n 為元素的個數，也就是數組（切片）的長度。為什麼會是 n – 1 而不是 n，因為到瞭第 n 輪，隻剩下最後一個元素沒有被固定，沒有元素可以和它進行比較瞭，因此第 n 輪可以忽略。

圖片演示

第一輪遍歷 [4, 2, 1, 3]

  • i = 0 時，比較第 i 個元素 4 與第 i + 1 個元素 2 的大小，因為 nums[i] > num[i+1]，也就是 4 > 2，因此交換它們的位置。
  • i = 1 時，4 > 1，互換位置。
  • i = 2 時，4 > 3，互換位置。最大值 4 被交換到最後一個位置，此時所有元素都參與比較過瞭，結束第一輪遍歷，執行下一輪遍歷。

第二輪遍歷 [2, 1, 3, 4]

  • i = 0 時，2 > 1，互換位置。
  • i = 1 時，2 < 3，不做交換。次大值 3 被交換到 4 的左邊，此時所有元素都參與比較過瞭，結束第二輪遍歷，執行下一輪遍歷。

第三輪遍歷 [1, 2, 3, 4]

  • i = 0 時，1 < 2，不做交換。此時所有元素都參與比較過瞭，結束第三輪遍歷，
  • 執行瞭 n – 1 輪遍歷，n 為數組的長度，n – 1個元素被交換到正確的位置，第 n 輪遍歷時，隻剩最後一個元素，因此不用繼續進行。

普通的冒泡排序算法

import "fmt"

func main() {
    nums := [4]int{4, 2, 1, 3}
    fmt.Println("原數組：", nums)
    fmt.Println("--------------------------------")
    NormalBubbleSort(nums)
}

func NormalBubbleSort(nums [4]int) {
    for i := 0; i < len(nums)-1; i++ {
        for j := 0; j < len(nums)-i-1; j++ {
            if nums[j] > nums[j+1] {
                    nums[j], nums[j+1] = nums[j+1], nums[j]
            }
        }
        fmt.Printf("第 %d 輪遍歷後的數組：%v\n", i+1, nums)
    }
    fmt.Println("--------------------------------")
    fmt.Println("排序後的數組：", nums)
}

執行結果：

原數組： [4 2 1 3]
——————————–
第 1 輪遍歷後的數組：[2 1 3 4]
第 2 輪遍歷後的數組：[1 2 3 4]
第 3 輪遍歷後的數組：[1 2 3 4]
——————————–
排序後的數組： [1 2 3 4]

值得註意的一個地方是第二層循環的條件 j < len(nums)-i-1，為什麼會減去 i，因為每輪遍歷結束之後，都會有一個元素被固定到後面，因此再進行下一輪的時候，那個元素無須再進行比較。

算法遍歷次數為 n -1，每次遍歷時元素比較的次數依次為 n – 1、n – 2、n – 3、···、3、2、1，將所有次數求和 = 1 + 2 + 3 + ··· + n – 2 + n – 1= n – 1 * (n – 1 + 1) / 2 = (n² – 1) / 2，因此時間復雜度為 O(n²)。

優化算法

上述例子中，對數組 [4,2,1,3] 進行排序，我們來看看對數組 [4,2,1,3,5] 進行排序，打印數組排序的變化過程中：

原數組： [4 2 1 3 5]
——————————–
第 1 輪遍歷後的數組：[2 1 3 4 5]
第 2 輪遍歷後的數組：[1 2 3 4 5]
第 3 輪遍歷後的數組：[1 2 3 4 5]
第 4 輪遍歷後的數組：[1 2 3 4 5]
——————————–
排序後的數組： [1 2 3 4 5]

不難看出，第三輪與第四輪遍歷過程中，都沒有進行元素交換位置的操作，對此我們可以推出一個結論，如果在一輪遍歷中，沒有進行元素交換位置的操作，那麼此時數組的裡所有元素都處於正確位置。 根據這個結論，我們可以對算法進行優化：

import "fmt"

func main() {
    nums := [5]int{4, 2, 1, 3, 5}
    fmt.Println("原數組：", nums)
    fmt.Println("--------------------------------")
    BestBubbleSort(nums)
}

func BestBubbleSort(nums [5]int) {
    isSwapped := true
    for isSwapped {
        isSwapped = false
        for i := 0; i < len(nums)-1; i++ {
            if nums[i] > nums[i+1] {
                nums[i], nums[i+1] = nums[i+1], nums[i]
                isSwapped = true
            }
        }
        fmt.Println("遍歷後的數組：", nums)
    }
    fmt.Println("--------------------------------")
    fmt.Println("排序後的數組：", nums)
}

執行結果：

原數組： 
——————————–
遍歷後的數組： [2 1 3 4 5]
遍歷後的數組： [1 2 3 4 5]
遍歷後的數組： [1 2 3 4 5]
——————————–
排序後的數組： [1 2 3 4 5]

  • 定義交換的標記變量 isSwapper，作為第一層循環的條件，每輪遍歷開始之後，將標記變量 isSwapper 賦值為 false，如果在比較的過程中發生元素交換，則將標記變量 isSwapper 賦值為 true。直到 isSwapper 為 false 時，數組的裡所有元素都處於正確的位置，此時可以結束遍歷瞭。
  • 根據執行結果可知，相比普通的算法，優化後的算法少瞭一輪遍歷，這隻是在數組元素少的情況下，如果在數組元素多的情況下，對比結果會更明顯。
  • 如果數組為 [5,1,2,3,4]，那麼算法隻會遍歷一輪，就能得到正確的排序結果。因此優化後的算法，最好的情況下時間復雜度為 O(N)，最壞的情況下仍為 O(N²)。

小結

本文首先對冒泡排序進行簡單的介紹，然後通過圖片演示冒泡排序的思路。普通冒泡排序算法一共要遍歷 n – 1 輪，由測試用例 [4 2 1 3 5] 的結果可以推斷出 如果在一輪遍歷中，沒有進行元素交換位置的操作，那麼此時數組的裡所有元素都處於正確位置。 根據這個結論，對算法進行優化，優化後的算法，最好的情況下時間復雜度為 O(N)。

到此這篇關於基於Go語言實現冒泡排序算法的文章就介紹到這瞭,更多相關Go語言冒泡排序內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：