什么是插入排序
顺序从序列中取一个数与左侧的元素们做比较,如果左侧的元素比取的数大,就向右移,直到把取的数插入到不小于左侧元素的位置处。
此种排序方法类似于你在打扑克牌的时候,整理纸牌顺序的做法。
时间复杂度
时间复杂度为O(n^2)
/************************************************************
** @Description: insertion
** @Author: haodaquan
** @Date: 2018-09-02 11:03
** @Last Modified by: haodaquan
** @Last Modified time: 2018-09-02 11:03
*************************************************************/
package insertion
func Sort(arr []int) []int {
len := len(arr)
if len < 2 {
return arr
}
for i := 1; i < len; i++ {
for j := i; j > 0; j-- {
if arr[j] < arr[j-1] {
arr[j-1], arr[j] = arr[j], arr[j-1]
}
}
}
return arr
}
测试代码和性能测试代码已经放到了github上,地址:
https://github.com/george518/PPGo_algorithm/tree/master/sort/insertion
不妨一试.