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

今天繼續(xù)介紹排序算法 —— 選擇排序。

實現(xiàn)原理

選擇排序算法的實現(xiàn)思路有點類似插入排序，也分已排序區(qū)間和未排序區(qū)間。但是選擇排序每次會從未排序區(qū)間中找到最小的元素，將其放到已排序區(qū)間的末尾。這樣一來，當(dāng)遍歷完未排序區(qū)間，就意味著已經(jīng)完成整個序列的排序了。圖示如下：

同樣，可以在 VisuAlgo 上看動態(tài)圖：https://visualgo.net/zh/sorting。

示例代碼

選擇排序的實現(xiàn)邏輯非常簡單，對應(yīng)的 Go 實現(xiàn)代碼如下：

package main

import "fmt"

func selectionSort(nums []int) {
    if len(nums) <= 1 {
        return
    }
    // 已排序區(qū)間初始化為空，未排序區(qū)間初始化待排序切片
    for i := 0; i < len(nums); i++ {
        // 未排序區(qū)間最小值初始化為第一個元素
        min := i
        // 從未排序區(qū)間第二個元素開始遍歷，直到找到最小值
        for j := i + 1; j < len(nums); j++ {
            if nums[j] < nums[min] {
                min = j
            }
        }
        // 將最小值與未排序區(qū)間第一個元素互換位置（等價于放到已排序區(qū)間最后一個位置）
        if min != i {
            nums[i],nums[min] = nums[min], nums[i]
        }
    }
}

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

由于傳遞到 selectionSort 函數(shù)的參數(shù)是 []int 類型的切片，而切片是引用類型，所以其實不必定義返回值，運行上述代碼，打印結(jié)果如下：

表明排序算法可以正常工作。

性能分析

接下來，我們來看看選擇排序的性能和穩(wěn)定性：

• 很顯然，選擇排序的時間復(fù)雜度也是 O(n²)

• 由于不涉及額外的存儲空間，所以是原地排序；

• 由于涉及非相鄰元素的位置交換，所以是不穩(wěn)定的排序算法。

綜合比較前面介紹的三種排序算法，時間復(fù)雜度都是一樣的，也都是原地排序，但是選擇排序是不穩(wěn)定的排序算法，此外，插入排序和冒泡排序相比較的話，插入排序只需要執(zhí)行一條語句，而冒泡排序需要三條，因此在同等條件下，或者數(shù)據(jù)量很大的情況下，插入排序性能是要略優(yōu)于冒泡排序的，所以綜合比較下來，三者的優(yōu)先級是插入排序 > 冒泡排序 >> 選擇排序。

不過三者的時間復(fù)雜度都是 O(n²)，在數(shù)據(jù)量很大的情況下性能表現(xiàn)其實都不理想，還可以進(jìn)一步進(jìn)行優(yōu)化，這就是我們接下來要介紹的歸并排序和快速排序算法。