Go 数据结构和算法篇（五）：插入排序

Go语言中文网 昨天

以下文章来源于xueyuanjun ，作者xueyuanjun

实现原理

今天继续介绍排序算法 —— 插入排序。

插入排序的原理是：我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

整体流程如下图所示：

插入排序图示

在这里搭配动态图查看效果更佳：https://visualgo.net/zh/sorting。

示例代码

插入排序也比较简单，对应的 Go 实现代码如下：

package main

import "fmt"

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

    for i := 0; i < len(nums); i++ {       // 每次从未排序区间取一个数据 value        value := nums[i]        // 在已排序区间找到插入位置        j := i - 1        for ; j >= 0; j-- {           // 如果比 value 大后移            if nums[j] > value {                nums[j+1] = nums[j]            } else {                break            }        }        // 插入数据 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)}

运行上述代码，打印结果如下：

性能分析

我们来看下插入排序的性能和稳定性：

• 插入排序需要两个嵌套的循环，时间复杂度是O(n²)；

• 没有额外的存储空间，是原地排序算法；

• 不涉及相等元素位置交换，是稳定的排序算法。

插入排序的时间复杂度和冒泡排序一样，也不是很理想，但是插入排序不涉及数据交换，从更细粒度来区分，性能要略优于冒泡排序。

（本文完）