插入排序（Insertion sort）是一种简单直观的排序算法。它的工作原理为将待排列元素划分为「已排序」和「未排序」两部分，每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。
从第二个元素开始，把前面的元素序列当作是已经有序的，然后寻找合适的位置插入。相比与冒泡排序和选择排序而言，比较的次数和数据交换的次数都得到了减少。
一个与插入排序相同的操作是打扑克牌时，从牌桌上抓一张牌，按牌面大小插到手牌后，再抓下一张牌。
优点：插入排序是普通排序里面效率最高的排序算法，而且在数据越趋于有序的情况下，插入排序的效率是最高的。
复杂度：插入排序的最优时间复杂度为 ，在数列几乎有序时效率很高。最坏时间复杂度和平均时间复杂度都为 。
代码实现