Go 实现插入排序算法及优化

简介: 本文首先对插入排序进行简单地介绍,通过图片来演示插入排序的过程,然后使用 Go 语言实现插入排序的算法。为减少算法中交换次数的逻辑,对算法进行优化,将交换的逻辑变成把前面的数往后移,最后将待排序的数插入到合适的位置即可。除了这种优化方式,还有一种改造方式:普通的算法往左查找的方式是线性查找,由于元素是有序的,因此线性查找可以换成二分查找,但是经过二分找到待插入的位置之后,也得移动前面的元素,相比上面的优化方法,还多了 O(logn) 的查找时间复杂度,因此我认为没有必要改造成二分查找。

耐心和持久胜过激烈和狂热。

哈喽大家好,我是陈明勇,本文分享的内容是使用 Go 实现插入排序算法。如果本文对你有帮助,不妨点个赞,如果你是 Go 语言初学者,不妨点个关注,一起成长一起进步,如果本文有错误的地方,欢迎指出!

插入排序

插入排序是一种简单的排序算法,以数组为例,我们可以把数组看成是多个数组组成。插入排序的基本思想是往前面已排好序的数组中插入一个元素,组成一个新的数组,此数组依然有序。光看文字可能不理解,让我们看看图示:

插入排序.png

插入排序的时间复杂度为 O(N²)。

算法实现

import (
    "fmt"
)
func main() {
    nums := [4]int{4, 1, 3, 2}
    fmt.Println("原数组:", nums)
    fmt.Println("--------------------------------")
    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("--------------------------------")
    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 变量的初值为 i 的值,由 j 变量往前去寻找待插入的位置;
  • 循环条件为 j > 0 && nums[j] < nums[j - 1]
  • j > 0 → 寻找到左边界则结束寻找;
  • nums[j] < nums[j - 1] → 左边元素小于待排序的元素则结束寻找;
  • 循环体为元素交换逻辑,只要满足循环条件,则不断交换元素,直到交换到待插入的位置,才终止。

算法优化

上面的代码,是通过不断地交换元素,直到无法交换,才能将元素放置到待插入的位置,为了避免频繁交换元素而导致效率低,将交换的逻辑变成把前面的数往后移,最后再将待排序的元素插入到合适的位置即可。

import (
    "fmt"
)
func main() {
    nums := [4]int{4, 1, 3, 2}
    fmt.Println("原数组:", nums)
    fmt.Println("--------------------------------")
    InsertionSort(nums)
}
func InsertionSort(nums [4]int) {
    for i := 1; i < len(nums); i++ {
        t := nums[i]
        j := i
        for ; j > 0 && t < nums[j-1]; j-- {
            nums[j] = nums[j-1]
        }
        nums[j] = t
        fmt.Printf("第 %d 轮后:%v\n", i, nums)
    }
    fmt.Println("--------------------------------")
    fmt.Println("排序后的数组:", nums)
}
复制代码
  • 用变量 t 记录待排序的元素,用 j 变量往前查找,只要前面的数比 t 大,那么就往后移,最后将 t 插入到合适的位置。

小结

  • 本文首先对插入排序进行简单地介绍,通过图片来演示插入排序的过程,然后使用 Go 语言实现插入排序的算法。为减少算法中交换次数的逻辑,对算法进行优化,将交换的逻辑变成把前面的数往后移,最后将待排序的数插入到合适的位置即可。
  • 除了这种优化方式,还有一种改造方式:普通的算法往左查找的方式是线性查找,由于元素是有序的,因此线性查找可以换成二分查找,但是经过二分找到待插入的位置之后,也得移动前面的元素,相比上面的优化方法,还多了 O(logn) 的查找时间复杂度,因此我认为没有必要改造成二分查找。
目录
相关文章
|
10天前
|
机器学习/深度学习 传感器 算法
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
98 14
|
9天前
|
存储 监控 算法
企业电脑监控系统中基于 Go 语言的跳表结构设备数据索引算法研究
本文介绍基于Go语言的跳表算法在企业电脑监控系统中的应用,通过多层索引结构将数据查询、插入、删除操作优化至O(log n),显著提升海量设备数据管理效率,解决传统链表查询延迟问题,实现高效设备状态定位与异常筛选。
39 3
|
10天前
|
机器学习/深度学习 运维 算法
【微电网多目标优化调度】多目标学习者行为优化算法MOLPB求解微电网多目标优化调度研究(Matlab代码实现)
【微电网多目标优化调度】多目标学习者行为优化算法MOLPB求解微电网多目标优化调度研究(Matlab代码实现)
|
10天前
|
算法 数据可视化 异构计算
【车辆路径问题VRPTW】基于北极海鹦优化(APO)算法求解带时间窗的车辆路径问题VRPTW研究(Matlab代码实现)
【车辆路径问题VRPTW】基于北极海鹦优化(APO)算法求解带时间窗的车辆路径问题VRPTW研究(Matlab代码实现)
|
10天前
|
机器学习/深度学习 运维 算法
【复现】基于改进秃鹰算法的微电网群经济优化调度研究(Matlab代码实现)
【复现】基于改进秃鹰算法的微电网群经济优化调度研究(Matlab代码实现)
|
10天前
|
机器学习/深度学习 算法 安全
【无人机三维路径规划】基于非支配排序的鱼鹰优化算法NSOOA求解无人机三维路径规划研究(Matlab代码实现)
【无人机三维路径规划】基于非支配排序的鱼鹰优化算法NSOOA求解无人机三维路径规划研究(Matlab代码实现)
|
10天前
|
机器学习/深度学习 负载均衡 算法
【柔性作业车间调度】基于四种多目标优化算法(NSOOA、NSPSO、NSDBO、NSCOA)求解柔性作业车间调度问题FJSP研究(Matlab代码实现)
【柔性作业车间调度】基于四种多目标优化算法(NSOOA、NSPSO、NSDBO、NSCOA)求解柔性作业车间调度问题FJSP研究(Matlab代码实现)
|
11天前
|
数据采集 机器学习/深度学习 运维
【故障诊断】基于负熵诱导灰狼优化算法的多目标信息频带选择用于滚动轴承故障诊断(Matlab代码实现)
【故障诊断】基于负熵诱导灰狼优化算法的多目标信息频带选择用于滚动轴承故障诊断(Matlab代码实现)
|
10天前
|
存储 编解码 算法
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
|
12天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)