第三种排序算法来了
问题
使用插入排序算法对列表中随机生成的10个数据进行从小到大排序，即最小的数字在最上面，最大的数字在最下面。
分析
其实只要你会玩扑克牌，就已经会插入排序了。我们打牌的时候，一般左手拿牌，右手去抓新牌。刚开始左手没有牌，拿一张在手里，不用排序；但你抓第二张牌的时候，一般就会和左手的牌比较一下，比它大，你会放右边；比它小，你就把它“插入”到左手这张牌的左边。这已经完成了第一次“插入排序”过程。以后我们每抓一张牌，都会左手牌的最右边一张向左扫描，找到合适的位置把新牌插入进去（当然，因为手里的牌很少，我们往往一眼扫过去就知道应该插在哪个位置了）。这个过程，我们就是重复地把桌子上的牌（未排序的）插入到左手中的牌（已排好序的），这样左手的牌始终是有序的。
计算机进行插入排序的过程，和它是非常类似的。我们现在让排队的小朋友再给我们演示一遍排队过程。
这次用插入排序的方式，第一位欢欢同学前面没有人，不需要插入，所以老师站在了第二位：
现在，老师要为第二位的可可寻找一个合适的位置插队。所以，可可会与左边的欢欢比较，发现比欢欢低，所以与欢欢交换了位置。交换完成之后，可可发现自己已经站在第一个位置了，插队结束：
现在，老师向前走一步，来到乐乐的位置，开始帮助乐乐寻找插队的位置：
乐乐比她前面的欢欢低，于是欢欢自觉地退了一步，让乐乐插队到他前面：
乐乐接着和前面的可可比，发现仍然可以插队，于是与可可交换位置：
目前为止，乐乐、可可、欢欢三个是排好队的序列。于是老师走到第四位同学格格身边：
很显然，格格会依次与前面的欢欢、可可、乐乐换位置，因为她最低，直到排到第一位，才算结束：
目前五个同学已经排好了四个，就差最后一个图图了，老师走到图图身边：
图图在寻找位置的时候，发现欢欢比他高，于是他与欢欢换了位置。然后呢，他发现前面的东西已经比他低了，他不能再向前插队了。于是，图图插队结束。
这时，老师再向前走一步，发现他已经走出了队伍的范围，没有同学需要再排队了，老师又一次完成了排队工作。
回顾上面的排序过程，你会发现老师是从第二位同学开始进行插队操作的，总共处理了四轮；在每一轮中，要么是这个同学已经排到第一位，要么是这个同学发现他前面的同学比他还低一些，总之是不必要再继续插队了，这一轮就结束。
编程
这里，我们把老师设置成变量 j ，让他从2开始，每次进行一轮插队，直至超出队伍的人数；在每一轮中，鸭子变量 j 从当前老师所在的位置开始，和前面的同学一一比较，如果已经是第一位，完成本轮排序；而如果发现这位同学排好队的比他小，也把鸭子变量设置为1，终止本轮排序。
看看程序运行效果：
总结
我们来看看插入排序比较了多少次：
- 第一轮：1次；
- 第二轮：2次；
- 第三轮：3次；
- 第四轮：1次；
总共：1+2+3+1=7次。好像比前面的冒泡排序和选择排序少一些？这是因为插入排序会省掉一部分比较操作（比如最后的图图，他并没有和其它所有同学比较）。在很多情况下，它确实比选择排序、冒泡排序要快一些。
