今天給大家介紹的是基于選擇的排序算法，常見(jiàn)基于選擇的排序算法有冒泡排序、插入排序、選擇排序、歸并排序和快速排序，我們?cè)谶x擇排序算法的時(shí)候，通常會(huì)根據(jù)以下幾個(gè)維度來(lái)考慮：

1. 時(shí)間復(fù)雜度

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

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

我們首先從冒泡排序開(kāi)始。

實(shí)現(xiàn)原理

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

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

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

示例代碼

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

package main

import "fmt"

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

    // 冒泡排序核心實(shí)現(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)
}

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

性能分析

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

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

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

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

時(shí)間復(fù)雜度是 O(n²)，看起來(lái)性能并不是很好，所以我們?cè)趯?shí)踐中基本不會(huì)選用冒泡算法。

（本文完）