复习2-插入排序

插入排序不复杂，简单来讲，相当于在洗完的牌堆里每次抽一张牌，放到手里和已有的牌排序。这里有三个假设：

1. 手里的牌已经是排好序的

2. 每次抽一张牌，按序列插入到已有的序列中

3. 直到抽完牌堆里所有的牌，排序结束

经过上面三步，完成了插入排序，算法复杂度最好的情况是O(n)，比如洗完的牌就是按顺序排放的，最坏的情况是O(n^2)，比如每次抽到的牌都是逆序的。那么该算法总体来说复杂度就是O(n^2)。

下面是golang实现的算法：

测试例子如下：

old arr:  [45 2 34 43 34 90 1 2 3 2 45 2 34 43 34 90 1 2 3 2]

new arr:  [1 1 2 2 2 2 2 2 3 3 34 34 34 34 43 43 45 45 90 90]

算法实现很容易理解，重点要处理好临界值特殊情况