插入排序不复杂,简单来讲,相当于在洗完的牌堆里每次抽一张牌,放到手里和已有的牌排序。这里有三个假设:
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]
算法实现很容易理解,重点要处理好临界值特殊情况
网友评论