vlambda博客
学习文章列表

上次有朋友问最近这些算法的文章受众是什么样的人？其实受众还是挺广泛的。有要打比赛的小学高年级到中学的学霸，以及各位愿意参与孩子学习的学霸家长；有大学计算机的学生；有准备考计算机研究生的人员；也可以是在职的程序员朋友；还有教编程的老师等等。

我们刚刚看完了和，今天再学习一下插入排序，依然是用之前的题目, 这样排列的6个数字。

通过插入排序，把这6个数字按照从左到右从小到大的顺序排列好，也就是目标是这样的：

插入排序的逻辑是假设这些数字中有一个有序的列表，然后不断往这个列表里插入新的数字。类似下图：

那一开始，我们也不知道这些数字当中有没有有序的列表怎么办？其实一开始只要把第一个数字作为有序的列表就可以，因为一个数字肯定是有序的。而后只要把右边其他数字依次插入到这个有序列表就可以。

下图中我们用两个红色竖线  框起来的数字是一个有序的列表，每次拿有序列表右侧的一个数字与有序列表当中的数字倒序进行比较，红色的线段是代表比较的，比较之后根据情况插入。

下面我们拆解一下具体执行步骤：

第一步，我们用5和有序列表中唯一的数字8进行比较，5比8小，所以把5挪到8前面，8向后挪动一位。

第二步，用3和有序列表中最后一个数字8进行比较，3比8小，接着把3和8前面数字5进行比较，3比5小，所以把3挪到5前面，5和8向后挪动一位。

第三步，用6和有序列表中最后一个数字8进行比较，6比8小，继续用6和5比较，5比6小，所以把6挪到8前面，8向后挪动一位。

......

大家也可以看看插入排序的视频便于更清晰的了解原理：

Play

1. 这个列表一上来就是完全有序的
   这种情况如果用倒序比较，每次每个数字只需要比较一次，这样只需要比较n-1次，n是列表数量。不需要任何移动。
   
2. 这个列表一上来是逆序排列的
   这种情况如果用倒序比较，第一次比较1次，移动1个元素（不考虑有序列表右侧元素的插入），第二次比较2次，移动2个元素，... 第n-1次比较n-1次，移动n-1个元素，所以一共比较移动了n(n-1)/2+n(n-1)/2=n(n-1)次，再加上每次有序列表右侧元素的插入操作，共2(n-1)次，所以就是n(n-1)+2(n-1)=n(n+1)-2次，总得来说与n²成正比。
   

   
   

完整代码如下：

下面再拆解下代码是如何做出来的：

1.插入排序时分成两部分数据，一部分是有序列表，一部分是有序列表右边的数据。

我们可以把有序列表右边第一位作为分界点，定义个变量i代表这个分界点。

然后我们的任务就是要去找有序列表当中的插入点来插入分界点的数据。下面这一步就是寻找插入点的代码片段，这段代码运行后变量j就是插入点。

2. 在插入点将分界点元素插入，插入点之后的所有元素后移一位。

3. 1，2两段代码组合就完成了一次比较和插入。之后循环对有序列表右侧所有元素进行处理就可以达成我们的最终目的，也就是开头的完整代码。

插入排序看起来也不难理解，现在我们已经写完了早期的三大排序算法，冒泡，选择和插入。究竟该选择哪种排序算法呢？我将在明天的推文里揭晓答案。