插入排序

插入排序(Insertion Sort) link

插入排序是一种基于比较的排序，每次迭代将无序列第一个元素插入到有序列中正确位置，直至序列中不存在无序列。

以升序为例介绍它的处理步骤:

• $i$指针指示无序列第一个元素。迭代范围$[1, n)$。
• $j$用于指示有序列中正确位置。从$i-1$往回迭代，记录正确位置。
• 循环寻找正确位置并插入，直至序列不存在无序列。