搜公众号
推荐 原创 视频 Java开发 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库
Lambda在线 > 代码笔记哥 > 摩根史丹利算法面试真题:插入排序

摩根史丹利算法面试真题:插入排序

代码笔记哥 2018-05-08
举报

   关注代码笔记哥有助于升职加薪噢!

欢迎来到笔记哥讲题 第6期

Insertion Sort

插入排序

摩根史丹利算法面试真题:插入排序
摩根史丹利算法面试真题:插入排序

     接上一期的内容,我们来复习另一个时间复杂度为O(n2)的比较排序:插入排序 (Insertion Sort) 。

题意

       给出一个无序整数数组,将其按从小到大的顺序排好。排序过程必须在给定数组内实现(in-place), 不可以额外开新的数组大小的空间。要求用插入排序完成。

 

样例:

输入: [2, 9, 5, 1]

输出: [1, 2, 5, 9]


思路

        “局部有序,挪移插入。”

 

       视频中提到“插入排序适用于数组局部有序这一场景”。这里补充一下,如果给定数组完全逆序,如 input array = [9,5,2,1] 我们仍可用插入排序;因为此时第一个数字9,可看做它对于它自己已经有序。只是在完全逆序情况下,插入排序的时间复杂度必然为O(n2),读者可以思考下这是为什么。


       详细讲解见视频。


视频

1. 腾讯视频链接

点击边框调出视频工具条
摩根史丹利算法面试真题:插入排序  


 2. YouTube链接

    墙外党请移步  https://youtu.be/ys6-TlRqAo8


长按上方二维码,关注Coding-Notes

获得美国顶尖金融与技术公司面试算法题

代码笔记哥,走心讲真题

将以更多原创优质内容

答谢您的赞赏

💗 赞赏入口请走左边 💗



版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《摩根史丹利算法面试真题:插入排序》的版权归原作者「代码笔记哥」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注代码笔记哥微信公众号

代码笔记哥微信公众号:Coding-Notes

代码笔记哥

手机扫描上方二维码即可关注代码笔记哥微信公众号

代码笔记哥最新文章

精品公众号随机推荐

举报