vlambda博客
学习文章列表

选择排序都完成了吗？

上面这段代码干什么的呢？“不知道！”（Google员工肯定知道，我吐槽一下）

它的意思是：如果你的回答是“true”，那就会在控制台打印出“完成了，真棒！”。

回归正题，我们已经学会了一种排序的方法——Selection sort，但它不是唯一的方法。你可能会说：“反正完成了就可以了，哼，太累。” 切记，我们是来学编程的！！！那我们就要有探究精神，let's roll！

现在要把你的大脑拽出来拍几下让它好好工作了，给它灌一杯咖啡或者茶也是不错的选择。甚至揍它一顿也行，只要你的大脑不因为负伤过重而罢工。清醒清醒，我们要开始分析判断了！

一、算法

我们现在介绍一个更高级的方法。想想下面的情况：

你现在身处太空小酒馆，手里拿着几张“从小到大”排序好的卡牌（比如1，2，3，4，5），然后一个粘液外星人给你另一张粘上了粘液的卡牌，你要把它放在正确的位置，让它们还是排好序。（我的意思不是你要把它放进垃圾桶里，或者塞回给那个外星人，这是不正确的）你会怎么放呢？

我们肯定会看看这个牌的数值，然后和已有的卡牌比较，最后把它放在正确的位置，对不对？

对。这就是一种新的算法，叫insertion sort（插入排序），也就是把牌插入正确的位置。不幸的是，你现在手上沾满了绿色的粘液，在用纸巾外星人的鼻子擦手，惹得他很生气，把绿色饮料倒在了你头上。哦，可怜的人，我们就先不看你了。

好啦，从你的外星人噩梦中挣脱出来，好好面对我们今天的任务。

二、插入函数

我们首先要做一个Insert function（插入函数）。这个函数能比较一个数和一个已经从小到大排好序的数组，将这个数正好插入到数组中，“比它小的”和“比它大的”两个数之间。Insert function的重点是要完好地保留所有数字，而且要把选定的数字放在正确的位置上。

为了实现这个，我们会从后往前，把这个数和数组中元素挨个比较，直到找到比它小的一个数。

比如，如果数是3，数组是（1，2，4，5），我们就会从5开始，往前找比3小的数，就会找到2。然后就把3插到2的后面。

我们怎么在数组里给3腾出一个位置呢？我们把比它大的这些数（就是4，5），全部往后挪一位，就可以了。

我们现在就得到了（1，2，3，4，5）。

很简单吧？请慢慢琢磨一下。

三、插入排序

下面来看插入排序的Pseudocode（伪码）。

Insertion Sort Pseudocode

1. 在整个数组中，先对数组中一位上的数和零位上的数，做上面的插入函数。

如下图中的（a），数组中一位上的数是“2”，零位上的数是“5”。注意数组是从零位开始的，要记住。

我们先将“2”和“5”比，发现“2”小于“5”，则将“2”放至零位，而零位上原来的“5”往后放一位。就是这样。

当然，如果一位上的数不比零位上的数小，则两数不动。

2. 然后，对数组中二位上的数，和“一位和零位“组成的数组，做上面的插入函数。

如上图中的（b），数组中二位上的数是“4”，零位和一位上的数是“2，5”。

我们就拿 “4” 和 “2，5” 比较。如前所述，插入函数就会把“4”插到“2，5”的中间。

3. 以此类推，如上图所示，从前往后，每次都将一个数，和它前面的数组，做插入函数，依次比较，找到它相应的位置，插入。直到数组的最后一位。我们就成功啦！

加油加油，加油加油！

请大家稍微思考思考，你们的IQ都很高，肯定能比得上粘液外星人和纸巾外星人，好好做吧！下次要学终极方法啦！

四、提示

1. 一定要注意数组开始为零这个小“坑”，运用你所学的就应该能解出来了。

   
   

2. 编程可以在khan学院网页里的编程器里编，也可以用vscode这个编程工具编，这样就可以一步一步观察代码是如何运行的，这就是debug（调试）。调试很有用的哦！、

   
   

3. 参考材料是khan学院的algorithm（算法）学习课程。网址是：https://www.khanacademy.org/computing/computer-science/algorithms（insertion sort 是第四课哦！）（英文好的可以参考上面这个，多看一看有好处）

     最后希望大家打起精神来，编完会很nice的！