Go 數(shù)據結構和算法篇（五）：插入排序

實現(xiàn)原理

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

插入排序的原理是：我們將數(shù)組中的數(shù)據分為兩個區(qū)間，已排序區(qū)間和未排序區(qū)間。初始已排序區(qū)間只有一個元素，就是數(shù)組的第一個元素。插入算法的核心思想是取未排序區(qū)間中的元素，在已排序區(qū)間中找到合適的插入位置將其插入，并保證已排序區(qū)間數(shù)據一直有序。重復這個過程，直到未排序區(qū)間中元素為空，算法結束。

整體流程如下圖所示：

在這里搭配動態(tài)圖查看效果更佳：https://visualgo.net/zh/sorting。

示例代碼

插入排序也比較簡單，對應的 Go 實現(xiàn)代碼如下：

package main

import "fmt"

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

    for i := 0; i < len(nums); i++ {
       // 每次從未排序區(qū)間取一個數(shù)據 value
        value := nums[i]
        // 在已排序區(qū)間找到插入位置
        j := i - 1
        for ; j >= 0; j-- {
           // 如果比 value 大后移
            if nums[j] > value {
                nums[j+1] = nums[j]
            } else {
                break
            }
        }
        // 插入數(shù)據 value
        nums[j+1] = value
    }

    return nums
}

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

運行上述代碼，打印結果如下：

性能分析

我們來看下插入排序的性能和穩(wěn)定性：

• 插入排序需要兩個嵌套的循環(huán)，時間復雜度是O(n²)；

• 沒有額外的存儲空間，是原地排序算法；

• 不涉及相等元素位置交換，是穩(wěn)定的排序算法。

插入排序的時間復雜度和冒泡排序一樣，也不是很理想，但是插入排序不涉及數(shù)據交換，從更細粒度來區(qū)分，性能要略優(yōu)于冒泡排序。