直接插入排序

登鹳雀楼

唐·王之涣

白日依山尽,黄河入海流。

 欲穷千里目,更上一层楼。

面试官:聊聊插入排序

插入排序是一种比较简单直观的排序算法,适用处理数据量比较少或者部分有序的数据,今天我们来聊聊插入排序。

排序思想

师傅,抄经书好无聊啊,要不咱们玩斗地主吧

一尘

慧能

好啊,但在此之前你先回答我几个问题

哦?什么问题

一尘

只见慧能拿出了一副牌,洗了洗牌,然后放在桌子上,从牌顶摸了几张牌

慧能

这些牌我已经手动排好序了

说着说着慧能又摸了一张牌

慧能

你说我这张红桃7该插入哪里呢?

红桃5和黑桃8之间

一尘

一尘不假思索地回答道

慧能

你是怎么判断要插入这里呢?

怎么判断?这一下还把小一尘给问愣住了,但是细想了一下整个过程,一尘答道

我觉得我的大脑是先将最后边的9和7比较,如果9大于7,则再拿8和7比较,直到找到不大于7(小于等于)的一张牌为止,然后将7插入到这张牌后面

一尘

慧能

恩恩,不错,这就是直接插入排序的主要思路

突然之间又学了一个知识点,每次知识都来得猝不及防,一尘心里想到

慧能

所谓直接插入排序,就是把未排序的元素一个一个地插入到有序的集合中,插入时就像你那样,把有序集合从后向前扫一遍,找到合适的位置插入

慧能拿来了笔和纸准备详细地说说

慧能

比如说我手中有这么一副牌

慧能

我把左边第一个8看做已经排好序的牌,右边的5,3,9都是未排好序的

慧能

然后我将5按照你的方法插入到排好序的集合中,显然,它会插到最左边

慧能

然后把3插入到排好序的集合

慧能

9同理

代码

哦,我懂了,原来直接插入排序这么简单

一尘

慧能

那你用代码实现一下呗

早知道就不说这句话了,一尘心里想,但师命难违,还是硬着头皮想了想

首先我用一个数组存储要排序的数据(无序)

然后我用for循环从前到后遍历整个数组,将无序元素一个一个地插入到正确的位置(排好序的位置),第一个元素我认为它是排好序的,所以我从第二个元素开始遍历

随后,小一尘写下了如下代码

数组下标从0开始,所以从1开始遍历,一直遍历到最后一个元素(arr.length-1)

一尘

一尘解释道

慧能

你这个插入到正确位置的函数是怎么实现的?

是啊,这个怎么实现呢?咦,我可以用一个临时变量把待插元素(将要插入到有序集合的元素)存起来,然后逐个和有序集合里的元素比较,如果集合里的元素大于待插元素,就将它向后移动一个单元,这样当遇到有序集合中小于等于待插元素的元素时就有地方放待插元素了

小一尘又把插入方法(insertToRightPosition)实现了

i 指向待插元素,j 会遍历有序数组中所有元素,直到找到合适的位置将待插元素(inserted)插入

一尘

慧能

恩恩,不错嘛!看来编码能力还行,那你说说你的这个代码的时间复杂度

时间复杂度

这个...,让我想想

一尘

下面讨论最坏时间复杂度,即所有元素倒序

这段代码最耗时的地方就花在最内层for循环里面的操作上(比较和移动)了,我只要大概估算出这些操作执行的次数就可以了

对于n个元素,首先我的外层for循环要循环n-1次

然后insertToRightPosition里的内层for循环的循环次数是根据 i 来决定的,i = 1时,循环 1 次,i = 2,循环 2 次,...,i = n-1,循环 n-1次,那总共加起来就是

根据复杂度计算规则,保留高阶项,并去掉系数,那么时间复杂度为O(n^2)

时间复杂度请看:

算法分析神器—时间复杂度

是O(n^2)

一尘

一尘说道

慧能

恩恩,不错,那算法的稳定性呢?

稳定性

是稳定的,因为在比较的时候,过两个数相等的话,不会进行移动,前后两个数的次序不会发生改变

一尘

慧能

恩恩,不错,走,下山玩斗地主去

好呀好呀

一尘

原文发布于微信公众号 - 趣谈编程(gh_51e791ad9174)

原文发表时间:2018-02-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户2442861的专栏

c++ 11 新特性

赖勇浩(http://laiyonghao.com) 声明:本文源自 Danny Kalev 在 2011 年 6 月 21 日发表的《The Bigges...

1101
来自专栏IT可乐

Java数据结构和算法(七)——链表

  前面博客我们在讲解数组中,知道数组作为数据存储结构有一定的缺陷。在无序数组中,搜索性能差,在有序数组中,插入效率又很低,而且这两种数组的删除效率都很低,并且...

4307
来自专栏开源优测

Python3希尔排序

希尔排序 概述 希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminshing Increment Sort),是直接插入排序算...

35610
来自专栏liulun

Nim教程【六】

目前看来这是国内第一个关于Nim的系列教程 先说废话 Rust1.0已经发布了, 国内有一个人为这个事情写了一篇非常长的博客, 这篇文章我前几天草草的看了...

2456
来自专栏苦逼的码农

从0打卡leetcode之day8--反转整数

假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231, 231 − 1]。根据这个假设,如果反转后的整数溢出,则返回 0。

1434
来自专栏猿人谷

常见排序算法分析

一.常见排序算法的实现 1.冒泡排序 冒泡排序是非常容易理解和实现,,以从小到大排序举例: 设数组长度为N。 1.比较相邻的前后二个数据,如果前面数据大于后面...

2058
来自专栏AI派

如何使用Python颠倒是非黑白?

有没有发现,打印 True 结果是 False,打印 False 结果是 True。是非黑白就在这么一瞬间颠倒了

771
来自专栏机器学习算法与Python学习

“基数排序”展现Python的优雅与简洁

在这儿那桶排序为例目的不是向大家介绍基数排序这种排序方式,是想通过基数排序的实现来展现Python的简洁与优雅。在这儿先简单的介绍一下基数排序,至于具体的内容会...

3445
来自专栏大前端开发

ES6特性之:参数默认值

作为一个开发者,跟进行业步伐是非常需要的,不能躺在现有的知识和经验温床上做美梦。JavaScript的ES2015标准(即我们说的ES6)在2016年已经被广泛...

874
来自专栏cmazxiaoma的架构师之路

Java数据结构与算法(4) -冒泡排序

1895

扫码关注云+社区

领取腾讯云代金券