插入排序

发布日期: 2022-04-22

文章字数: 542

阅读时长: 2 分钟

阅读次数:

实现原理

插入排序的原理是：我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
整体流程如下图所示：

动图演示

示例代码

插入排序也比较简单，对应的 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)
}