Press "Enter" to skip to content

Go 数据结构和算法篇(五):插入排序

实现原理

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

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

整体流程如下图所示:

插入排序图示

在这里搭配动态图查看效果更佳: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)
}

运行上述代码,打印结果如下:

-w589

性能分析

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

  • 插入排序需要两个嵌套的循环,时间复杂度是O(n2);
  • 没有额外的存储空间,是原地排序算法;
  • 不涉及相等元素位置交换,是稳定的排序算法。

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

发表回复