算法原理:
将一个记录插入到已排好序的序列中，从而得到一个新的有序序列（将序列的第一个数据看成是一个有序的子序列，然后从第二个记录逐个向该有序的子序列进行有序的插入，直至整个序列有序）
文章插图
算法实现(Go语言):
func insertSort(input []int) []int{ length := len(input) if length <= 0 { return input } for i:= 1 ;i < length; i++{ tmp := input[i] var j int for j= i-1; j >= 0 ; j-- { //因为是有序的，比tmp小，所以tmp要直接放在最后 if input[j] <= tmp { break } //tmp大,在tmp后的都要后移一位 if input[j] > tmp { input[j+1] = input[j] } } input[j + 1] = tmp } return input}复杂度
时间复杂度： 两层循环，外层循环n-1次 。第2层循环次数依赖于在第i个记录前的元素中小于第i个记录元素的个数 。
最差情况:每个元素都要移动到最前面(逆序的情况),时间复杂度为O(n^2)
最好情况:第2层循环直接break(已经正序的情况),时间复杂度为O(n)
空间复杂度：没有利用新的数组来帮助完成排序算法，所以空间复杂度为O(1)
【排序算法：直接插入排序】
推荐阅读
- 排序---堆排序
- 搜索引擎算法：谷歌算法
- PHP理论知识之12种排序算法的比较
- 牛人发明家用净水器，自来水进去，7重过滤，出来的水可直接喝
- 刀片扔垃圾桶怎么处理 不要的美工刀能直接丢在垃圾桶里吗
- 如何正确选择聚类算法？
- 什么是算法？如何学习算法？算法入门的学习路径
- 唯一ID生成算法剖析，看看这篇就够了
- 算法：如何实现大正整数相加？
- 香水喷衣服上可以吗 衣物香氛喷雾直接喷到衣服上吗