冒泡排序

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

• 遍歷數(shù)組，相鄰的兩個元素進行比較，以升序為例，如果前面的元素大于后面的元素，則將它們的位置進行交換
• 第一輪遍歷結(jié)束之后，最大的元素會處于所遍歷范圍的最后一個位置，然后繼續(xù)下一輪遍歷
• 每輪都會固定一個元素，直到所有元素都被固定，因此會執(zhí)行 n - 1輪，n 為元素的個數(shù)，也就是數(shù)組（切片）的長度。為什么會是 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 被交換到最后一個位置，此時所有元素都參與比較過了，結(jié)束第一輪遍歷，執(zhí)行下一輪遍歷。

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

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

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

• i = 0 時，1 < 2，不做交換。此時所有元素都參與比較過了，結(jié)束第三輪遍歷，
• 執(zhí)行了 n - 1 輪遍歷，n 為數(shù)組的長度，n - 1個元素被交換到正確的位置，第 n 輪遍歷時，只剩最后一個元素，因此不用繼續(xù)進行。

普通的冒泡排序算法

import "fmt"

func main() {
    nums := [4]int{4, 2, 1, 3}
    fmt.Println("原數(shù)組：", 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 輪遍歷后的數(shù)組：%v\n", i+1, nums)
    }
    fmt.Println("--------------------------------")
    fmt.Println("排序后的數(shù)組：", nums)
}

執(zhí)行結(jié)果：

原數(shù)組： [4 2 1 3]
--------------------------------
第 1 輪遍歷后的數(shù)組：[2 1 3 4]
第 2 輪遍歷后的數(shù)組：[1 2 3 4]
第 3 輪遍歷后的數(shù)組：[1 2 3 4]
--------------------------------
排序后的數(shù)組： [1 2 3 4]

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

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

優(yōu)化算法

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

原數(shù)組： [4 2 1 3 5]
--------------------------------
第 1 輪遍歷后的數(shù)組：[2 1 3 4 5]
第 2 輪遍歷后的數(shù)組：[1 2 3 4 5]
第 3 輪遍歷后的數(shù)組：[1 2 3 4 5]
第 4 輪遍歷后的數(shù)組：[1 2 3 4 5]
--------------------------------
排序后的數(shù)組： [1 2 3 4 5]

不難看出，第三輪與第四輪遍歷過程中，都沒有進行元素交換位置的操作，對此我們可以推出一個結(jié)論，如果在一輪遍歷中，沒有進行元素交換位置的操作，那么此時數(shù)組的里所有元素都處于正確位置。 根據(jù)這個結(jié)論，我們可以對算法進行優(yōu)化：

import "fmt"

func main() {
    nums := [5]int{4, 2, 1, 3, 5}
    fmt.Println("原數(shù)組：", 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("遍歷后的數(shù)組：", nums)
    }
    fmt.Println("--------------------------------")
    fmt.Println("排序后的數(shù)組：", nums)
}

執(zhí)行結(jié)果：

原數(shù)組： 
--------------------------------
遍歷后的數(shù)組： [2 1 3 4 5]
遍歷后的數(shù)組： [1 2 3 4 5]
遍歷后的數(shù)組： [1 2 3 4 5]
--------------------------------
排序后的數(shù)組： [1 2 3 4 5]

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

小結(jié)

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

到此這篇關(guān)于基于Go語言實現(xiàn)冒泡排序算法的文章就介紹到這了,更多相關(guān)Go語言冒泡排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論