Go语言中的插入排序详解（深入理解插入排序的时间复杂度与实现）

Go语言实现插入排序

下面是一个使用 Go 语言编写的插入排序函数：

func insertionSort(arr []int) {    for i := 1; i < len(arr); i++ {        key := arr[i]        j := i - 1        // 将大于 key 的元素向右移动        for j >= 0 && arr[j] > key {            arr[j+1] = arr[j]            j--        }        // 插入 key 到正确位置        arr[j+1] = key    }}

使用示例：

package mainimport "fmt"func insertionSort(arr []int) {    for i := 1; i < len(arr); i++ {        key := arr[i]        j := i - 1        for j >= 0 && arr[j] > key {            arr[j+1] = arr[j]            j--        }        arr[j+1] = key    }}func main() {    nums := []int{5, 2, 4, 6, 1, 3}    fmt.Println("排序前:", nums)    insertionSort(nums)    fmt.Println("排序后:", nums)}

插入排序的时间复杂度分析

理解插入排序时间复杂度是掌握该算法的关键：

• 最好情况：当输入数组已经有序时，内层循环不会执行，时间复杂度为 O(n)。
• 最坏情况：当输入数组完全逆序时，每次插入都需要比较并移动所有已排序元素，时间复杂度为 O(n²)。
• 平均情况：随机排列的数组，平均时间复杂度也是 O(n²)。

虽然插入排序在大数据集上效率不高，但它具有以下优点：

• 原地排序（空间复杂度为 O(1)）
• 稳定排序（相等元素的相对位置不变）
• 对小规模数据或基本有序的数据效率很高

为什么学习插入排序？

尽管现代应用中很少直接使用插入排序处理大规模数据，但它是理解更复杂算法（如希尔排序）的基础。同时，在 Go 语言标准库的某些排序实现中，对于小数组也会使用插入排序作为优化手段。

通过本教程，你不仅学会了如何用 Go语言插入排序，还掌握了其核心思想和 时间复杂度 特性。希望这篇 Go排序算法教程 能帮助你打下坚实的算法基础！

记住：算法学习贵在理解原理，动手实践。快去试试修改代码，观察不同输入下的运行效果吧！