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

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

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

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

整體流程如下圖所示：

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

示例代碼

插入排序也比較簡單，對應(yīng)的 Go 實(shí)現(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ū)間取一個(gè)數(shù)據(jù) 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ù)據(jù) 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)
}

運(yùn)行上述代碼，打印結(jié)果如下：

性能分析

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

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

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

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

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