Go 數(shù)據(jù)結(jié)構(gòu)和算法篇（四）：冒泡排序

今天給大家介紹的是基于選擇的排序算法，常見基于選擇的排序算法有冒泡排序、插入排序、選擇排序、歸并排序和快速排序，我們在選擇排序算法的時候，通常會根據(jù)以下幾個維度來考慮：

1. 時間復(fù)雜度

2. 空間復(fù)雜度（對內(nèi)存空間的消耗）

3. 算法的穩(wěn)定性（如果待排序的序列中存在值相等的元素，經(jīng)過排序之后，相等元素之間原有的先后順序不變）

我們首先從冒泡排序開始。

實現(xiàn)原理

冒泡排序只會操作相鄰的兩個數(shù)據(jù)。每次冒泡操作都會對相鄰的兩個元素進(jìn)行比較，看是否滿足大小關(guān)系要求，如果不滿足就讓它倆互換。一次冒泡會讓至少一個元素移動到它應(yīng)該在的位置，重復(fù) n 次，就完成了 n 個數(shù)據(jù)的排序工作。

光看定義有點抽象，我們用圖來演示，假設(shè)待排序數(shù)字是 4、5、6、3、2、1，第一次排序的流程是這樣的：

看這個圖的時候要結(jié)合定義一起看，否則也比較懵逼，當(dāng)然如果你去 VisuAlgo 上看動態(tài)圖的話就更形象了：https://visualgo.net/zh/sorting，經(jīng)過 n 次冒泡，最終完成排序（所謂冒泡，以升序來看，就是每次把待排序序列中的最大值插到已排序序列的最前面，這個過程就像冒泡一樣）：

示例代碼

重要的是理解冒泡排序的原理，懂了原理就是把這個排序過程翻譯成代碼而已，以下是 Go 代碼實現(xiàn)的冒泡排序：

package main

import "fmt"

func bubbleSort(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }

    // 冒泡排序核心實現(xiàn)代碼
    for i := 0; i < len(nums); i++ {
        flag := false
        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]
                flag = true
            }
        }
        if !flag {
            break
        }
    }

    return nums
}

func main() {
    nums := []int{4, 5, 6, 7, 8, 3, 2, 1}
    nums = bubbleSort(nums)
    fmt.Println(nums)
}

這里我們使用切片類型來存儲待排序數(shù)據(jù)序列，并且可以看到，我們對冒泡排序有個小小的優(yōu)化，就是當(dāng)某一次遍歷的時候發(fā)現(xiàn)沒有需要交換的元素，則認(rèn)為整個序列已經(jīng)排序完成。

性能分析

最后我們來看下冒泡排序的性能和穩(wěn)定性：

1. 時間復(fù)雜度：O(n²)

2. 空間復(fù)雜度：只涉及相鄰元素的交換，是原地排序算法

3. 算法穩(wěn)定性：元素相等不會交換，是穩(wěn)定的排序算法

時間復(fù)雜度是 O(n²)，看起來性能并不是很好，所以我們在實踐中基本不會選用冒泡算法。

（本文完）

推薦閱讀

• Go 數(shù)據(jù)結(jié)構(gòu)和算法篇（三）：隊列