go语言插入排序

smallBird · · 1756 次点击 · 开始浏览    置顶
这是一个创建于 的主题,其中的信息可能已经有所发展或是发生改变。

# go语言插入排序 ## 1 定义 ​ 插入排序 实际上就是在有序的数据中找到属于你自己的位置。基本思想: 将一个记录插入到一个有序表中 ## 2 理解 ​ 生活中有许多插入排序的例子。 ​ 例如:打扑克牌,我们正常人的思路都是: 第一张牌其实已经有序。所以不需要在排。 当拿到第二张牌的时候。就开始比较。正常来讲拿在我们手上的牌是不动的,那么我们需要决定这个第二张牌的位置,放前面还是后面。当第二张牌大,放后面,反之,放前面。 当拿到第三张牌的时候, 其实我们肉眼以及大脑是可以瞬间分析出来他的位置。但分析很简单。我们从最前面看到最后面。 每个和第三张牌比较一下。 然后具体的位置才有了。 以此类推 ## 3 过程 ​ 插入排序的算法实现过程: ![image.png](https://static.studygolang.com/200723/abc9a46ded5dd939103e7d2561e7db0d.png) 由图可得,每次取一个数,这个数和前一位进行比较,比前一个dada,交换,一直比,一直交换,直到前一个数比他大或者到第一个数了。结束比较和交换。 ## 4 时间复杂度 ​ 时间复杂度取决于 数据本身的有序性, ​ 如果数据基本有序,意味这O(n).因为每次和最后一次比较时,发现比他大,然后结束比较直接进入下一个数的比较,一共比较n次。则 n X 1 为 n 次。因此O(n) ​ 如果数据反序,那么,第一次要比较1 次,第二次比较2次,第三次比较3次,因此时间复杂度时n x (1+n)/2,因此是O(n2) 其他情况介于这两个之间。 ## 5 代码 ```go func insertSort(a []int)[]int{ for i:=1;i<len(a);i++{ temp := a[i] j := i-1 for j >= 0 && a[j] > temp { a[j+1] = a[j] j-- } if j != i-1 { a[j+1] = temp } } return a } ```

有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1756 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传