Go语言实现插入排序及优化策略

插入排序的原理

插入排序的基本思想是将数组视为已排序和未排序两部分。初始时，第一个元素被视为已排序部分，随后依次将未排序部分的元素插入到已排序部分的合适位置，使已排序部分始终保持有序状态。这种“逐个插入”的过程直至所有元素处理完毕，整个数组即变为有序。

插入排序的平均和最差时间复杂度均为 $O(N^2)$，在数据量较小或部分数据已基本有序的情况下表现优异。它也是一种稳定排序算法，相等元素的相对位置在排序前后不会改变。

基础版算法实现

最直观的实现方式是通过不断交换相邻元素，将当前待插入的元素逐步“冒泡”到正确的位置。以下是Go语言的基础实现代码：

import (
    "fmt"
)

func main() {
    nums := [4]int{4, 1, 3, 2}
    fmt.Println("原数组：", nums)
    InsertionSort(nums)
}

func InsertionSort(nums [4]int) {
    for i := 1; i < len(nums); i++ {
        // 内层循环：向前比较并交换
        for j := i; j > 0 && nums[j] < nums[j-1]; j-- {
            nums[j], nums[j-1] = nums[j-1], nums[j]
        }
        fmt.Printf("第 %d 轮后：%v\n", i, nums)
    }
    fmt.Println("排序后的数组：", nums)
}

执行结果：
原数组： [4 1 3 2]
第 1 轮后：[1 4 3 2]
第 2 轮后：[1 3 4 2]
第 3 轮后：[1 2 3 4]
排序后的数组： [1 2 3 4]

逻辑解析：

• 外层循环（变量 i）：表示当前待处理的元素索引，从第二个元素开始遍历至数组末尾。
• 内层循环（变量 j）：用于在已排序子数组中查找插入位置。起始值为 j = i，向左遍历。循环条件 j > 0 && nums[j] < nums[j-1] 确保：
• j > 0：防止越界访问；
• nums[j] < nums[j-1]：若当前元素小于前一个元素，则继续向前寻找。
• 元素交换：只要满足上述条件，就交换 nums[j] 和 nums[j-1]，直到找到正确的插入点。

算法优化：减少交换开销

基础版本虽然逻辑清晰，但每次比较后都进行一次交换操作，这在元素数量较多时会产生不必要的读写开销。优化的思路是：先记录当前待插入元素，然后将已排序区间内大于该元素的值统一向后移动一位，最后再将待插入元素放到腾出的空位上。

这种“后移法”将一次交换（涉及三次赋值）简化为多次赋值（仅涉及覆盖和最终回填），显著提升了运行效率。

func InsertionSortOptimized(nums [4]int) {
    for i := 1; i < len(nums); i++ {
        t := nums[i] // 记录待插入元素
        j := i       
        // 将比 t 大的元素往后移
        for ; j > 0 && t < nums[j-1]; j-- {
            nums[j] = nums[j-1]
        }
        nums[j] = t // 将 t 放入最终确定的位置
        fmt.Printf("第 %d 轮后：%v\n", i, nums)
    }
}

进阶思考：二分插入排序

由于已排序区间本身是有序的，理论上可以使用二分查找来确定插入位置，从而将比较次数降至 $O(\log n)$。然而，确定位置后仍然需要移动大量的后续元素来腾出空间，移动操作的复杂度仍为 $O(n)$。因此，在整体 $O(N^2)$ 的时间复杂度下，引入二分查找带来的额外对数级查找开销往往得不偿失。对于大多数实际应用场景，上述的线性后移优化已经足够高效。

以上就是基于Go语言实现插入排序算法及优化的详细内容，更多关于Go语言算法实战的资料请关注本站其它相关文章！