NOIP 普及组初赛 · NOIP 2011 普及组初赛试题 第 8 题

体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走到排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（ ）算法。

别被'排队'表象绕晕，直接抓核心动作：新同学来了，在已排好的队伍里找个合适位置插进去。这就是插入排序的本质——每次把新元素插入到已排序序列的正确位置。

很多同学看到'排尾走到排头'就联想到冒泡排序，因为冒泡也是从头到尾处理。但冒泡的核心是相邻交换，把大的往后沉；而本题是'找到第一个比自己高的就停，插在他后面'，这是典型的'找位置插入'。再有人可能误选快排或归并，那是分治思想，跟这种线性插入过程完全不一样。

这道题考什么

这道题考查的是对插入排序（Insertion Sort）这一基础排序算法的理解和类比能力。

核心概念：什么是插入排序

插入排序的核心思想非常简单：假设我们已经有一个排好序的序列，现在来一个新的元素，我们只需要在已有的序列中找到这个新元素应该插入的位置，然后把它插进去，这样新序列依然有序。

比如手里有一副已经排好序的牌，再来一张新牌，你只需要把它插到合适的位置，整副牌就重新排好了。