冒泡排序

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

• 遍歷數(shù)組，相鄰的兩個(gè)元素進(jìn)行比較，以升序?yàn)槔绻懊娴脑卮笥诤竺娴脑兀瑒t將它們的位置進(jìn)行交換
• 第一輪遍歷結(jié)束之后，最大的元素會(huì)處于所遍歷范圍的最后一個(gè)位置，然后繼續(xù)下一輪遍歷
• 每輪都會(huì)固定一個(gè)元素，直到所有元素都被固定，因此會(huì)執(zhí)行 n - 1輪，n 為元素的個(gè)數(shù)，也就是數(shù)組（切片）的長(zhǎng)度。為什么會(huì)是 n - 1 而不是 n，因?yàn)榈搅说?n 輪，只剩下最后一個(gè)元素沒(méi)有被固定，沒(méi)有元素可以和它進(jìn)行比較了，因此第 n 輪可以忽略。

圖片演示

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

• i = 0 時(shí)，比較第 i 個(gè)元素 4 與第 i + 1 個(gè)元素 2 的大小，因?yàn)?nums[i] > num[i+1]，也就是 4 > 2，因此交換它們的位置。
• i = 1 時(shí)，4 > 1，互換位置。
• i = 2 時(shí)，4 > 3，互換位置。最大值 4 被交換到最后一個(gè)位置，此時(shí)所有元素都參與比較過(guò)了，結(jié)束第一輪遍歷，執(zhí)行下一輪遍歷。

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

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

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

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

普通的冒泡排序算法

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]

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

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

優(yōu)化算法

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

原數(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]

不難看出，第三輪與第四輪遍歷過(guò)程中，都沒(méi)有進(jìn)行元素交換位置的操作，對(duì)此我們可以推出一個(gè)結(jié)論，如果在一輪遍歷中，沒(méi)有進(jìn)行元素交換位置的操作，那么此時(shí)數(shù)組的里所有元素都處于正確位置。 根據(jù)這個(gè)結(jié)論，我們可以對(duì)算法進(jìn)行優(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)的條件，每輪遍歷開(kāi)始之后，將標(biāo)記變量 isSwapper 賦值為 false，如果在比較的過(guò)程中發(fā)生元素交換，則將標(biāo)記變量 isSwapper 賦值為 true。直到 isSwapper 為 false 時(shí)，數(shù)組的里所有元素都處于正確的位置，此時(shí)可以結(jié)束遍歷了。
• 根據(jù)執(zhí)行結(jié)果可知，相比普通的算法，優(yōu)化后的算法少了一輪遍歷，這只是在數(shù)組元素少的情況下，如果在數(shù)組元素多的情況下，對(duì)比結(jié)果會(huì)更明顯。
• 如果數(shù)組為 [5,1,2,3,4]，那么算法只會(huì)遍歷一輪，就能得到正確的排序結(jié)果。因此優(yōu)化后的算法，最好的情況下時(shí)間復(fù)雜度為 O(N)，最壞的情況下仍為 O(N2)。

小結(jié)

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