基于Go语言实现插入排序算法及优化

作者:陈明勇 时间:2024-05-22 10:18:05 

插入排序

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

基于Go语言实现插入排序算法及优化

插入排序的时间复杂度为 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]

1.第一层循环的 i 变量,表示待排序的元素;

2.第二层循环:

j 变量的初值为 i 的值,由 j 变量往前去寻找待插入的位置;

  • 循环条件为 j > 0 && nums[j] < nums[j - 1]

  • j > 0 &rarr; 寻找到左边界则结束寻找;

nums[j] < nums[j - 1] &rarr; 左边元素小于待排序的元素则结束寻找;

3.循环体为元素交换逻辑,只要满足循环条件,则不断交换元素,直到交换到待插入的位置,才终止。

算法优化

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

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) 的查找时间复杂度,因此我认为没有必要改造成二分查找。

来源:https://juejin.cn/post/7175178438095929404

标签:Go,插入排序
0
投稿

猜你喜欢

  • Python类绑定方法及非绑定方法实例解析

    2022-08-10 11:36:38
  • Python获取邮件地址的方法

    2022-05-29 10:53:05
  • Python matplotlib画图实例之绘制拥有彩条的图表

    2023-01-26 02:06:25
  • MobaXterm详细使用图文教程(MobaXterm连接Linux服务器)

    2023-05-07 05:51:43
  • JavaScript 中的 Base64 编码(一):Encode

    2010-07-23 10:16:00
  • python爬虫selenium模块详解

    2023-04-11 20:32:43
  • 对pandas中两种数据类型Series和DataFrame的区别详解

    2021-08-05 04:09:38
  • 浅谈Scrapy框架普通反爬虫机制的应对策略

    2023-07-14 17:11:40
  • 10个python爬虫入门实例(小结)

    2021-04-21 01:08:57
  • js中火星坐标、百度坐标、WGS84坐标转换实现方法示例

    2024-04-25 13:12:57
  • HTTP提交方式之PUT详细介绍及POST和PUT的区别

    2022-08-21 16:23:44
  • 友情连接地址代码-线线表格

    2010-07-01 16:26:00
  • Django实现内容缓存实例方法

    2021-04-19 20:47:41
  • 使用PyInstaller库把Python程序打包成exe

    2023-11-27 17:40:28
  • Node.js中创建和管理外部进程详解

    2024-05-02 17:36:03
  • js格式化金额可选是否带千分位以及保留精度

    2023-10-06 04:03:14
  • python实现数独算法实例

    2022-11-12 05:31:12
  • Blender Python编程实现程序化建模生成超形示例详解

    2023-06-14 14:38:53
  • 浅谈Python面向对象编程oop思想心得

    2021-10-25 16:45:29
  • 在MySQL中使用LIMIT进行分页的方法

    2024-01-20 22:27:58
  • asp之家 网络编程 m.aspxhome.com