美文网首页
复习2-插入排序

复习2-插入排序

作者: 董泽润 | 来源:发表于2016-07-05 11:16 被阅读55次

插入排序不复杂,简单来讲,相当于在洗完的牌堆里每次抽一张牌,放到手里和已有的牌排序。这里有三个假设:

1. 手里的牌已经是排好序的

2. 每次抽一张牌,按序列插入到已有的序列中

3. 直到抽完牌堆里所有的牌,排序结束

经过上面三步,完成了插入排序,算法复杂度最好的情况是O(n),比如洗完的牌就是按顺序排放的,最坏的情况是O(n^2),比如每次抽到的牌都是逆序的。那么该算法总体来说复杂度就是O(n^2)。

下面是golang实现的算法:

插入排序

测试例子如下:

old arr:  [45 2 34 43 34 90 1 2 3 2 45 2 34 43 34 90 1 2 3 2]

new arr:  [1 1 2 2 2 2 2 2 3 3 34 34 34 34 43 43 45 45 90 90]

算法实现很容易理解,重点要处理好临界值特殊情况

相关文章

  • 复习2-插入排序

    插入排序不复杂,简单来讲,相当于在洗完的牌堆里每次抽一张牌,放到手里和已有的牌排序。这里有三个假设: 1. 手里的...

  • 173. 链表插入排序

    用插入排序对链表排序样例Given 1->3->2->0->null, return 0->1->2->3->nu...

  • 排序第二记——插入排序(插入、Shell排序)

    这次直入主题,我今天要复习的是插入排序!插入排序分为“直接插入”和“Shell排序”,Shell排序就是希尔排序,...

  • OJ lintcode 链表插入排序

    用插入排序对链表排序您在真实的面试中是否遇到过这个题?Yes样例Given 1->3->2->0->null, r...

  • 插入排序

    考研时候复习严蔚敏的数据结构,发现还有好多自己不会的东西,甚至连插入排序都忘了。特别尴尬。插入排序的思路很简单,假...

  • 算法踩坑6-二叉搜索树排序

    背景 接上面五篇文章算法踩坑-快速排序 算法踩坑2-插入排序 算法踩坑3-堆排序 算法踩坑4-冒泡排序 ...

  • 算法复习之——插入排序

    原理 1.定义一个指针,将指针指向某个元素(一般指向第二个),然后把以这个元素为基准,将整个数组分成两个部分,左侧...

  • 算法踩坑5-归并排序

    背景 接上面四篇文章算法踩坑-快速排序 算法踩坑2-插入排序 算法踩坑3-堆排序 算法踩坑4-冒泡排序 来...

  • 如何复习韩语效果佳?

    1-及时反复复习韩语 一般来说,上午学的内容晚上复习,下午或者晚上学习的内容第二天早上复习,效果自然佳。 2-适...

  • 算法踩坑2-插入排序

    背景 接上面一篇文章 算法踩坑-快速排序 来继续聊聊最近我写的一些算法的小例程。主要从以下几方面来说的: 插入排序...

网友评论

      本文标题:复习2-插入排序

      本文链接:https://www.haomeiwen.com/subject/jyehjttx.html