直接插入排序

中华

诗词

登鹳雀楼

唐·王之涣

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

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

面试官：聊聊插入排序

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

排序思想

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

一尘

慧能

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

哦？什么问题

一尘

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

慧能

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

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

慧能

你说我这张红桃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)

一尘

一尘说道

慧能

恩恩，不错，那算法的稳定性呢？

稳定性

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

一尘

慧能

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

好呀好呀

一尘

关于稳定性可以看：冒泡排序（文末有）