C++第18天:排序算法之-插入排序（十大排序算法菜鸟教程）

挑战暑假自学C++的第18天。

前面已经学习过两种排序方法了，今天要了解的插入排序对于大家来说应该也不难。说起插入排序，我相信只要是玩过扑克牌或者麻将的朋友都知道它的原理。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列。

·对于未排序的数据，在已排序序列中从后向前扫描，找到相应的位置并插入。会发现它会将待排列的一个元素先提出来，从后往前找，在合适的位置放回去，重复这个操作，直到最后一个元素也回到合适的位置为止。确实很像扑克牌抓牌，于是就可以开始写代码了。

·在主函数里只是将选择排序的函数换成了插入排序，print打印函数的内容没有变，所以来看插入函数的具体内容。

→首先要假定第0个元素已经是有序的，所以从第1个元素开始排序到最后一个元素结束，总轮数还是n-1轮不变。

→接着把待排列的元素提出来，暂存到变量key中。

→接下来就与前面的元素开始比较，因为并不能预估每个元素会比较多少次，所以这里用while循环比较好。可以看出循环的条件是还没有找到队首，并且前一个元素比key要大，就要继续往前找。

→为此就要依次将无序元素往后挪一位，直到找到合适的位置为止。

→将key中缓存的值放到队列中就可以了。

这就是今天的全部内容，欢迎截图保存自行练习。respect，明天继续，明天见。