[golang] 数据结构-二分插入排序
发布时间:2020-12-16 09:34:39 所属栏目:大数据 来源:网络整理
导读:接上文 直接插入排序 直接插入排序每轮比较中,都需要把待处理的元素与前面每一位元素进行比较。那么有没有一种方法可以优化下,减少比较次数呢?答案当然是有的,下面介绍的二分插入就是直接插入排序的优化算法之一。 原理 直接插入排序是挨个的去比较,而
接上文
直接插入排序
直接插入排序每轮比较中,都需要把待处理的元素与前面每一位元素进行比较。那么有没有一种方法可以优化下,减少比较次数呢?答案当然是有的,下面介绍的二分插入就是直接插入排序的优化算法之一。 原理 复杂度 代码实现 package main import ( "fmt" "math/rand" "time" ) func main() { var length = 10 var list []int // 以时间戳为种子生成随机数,保证每次运行数据不重复 r := rand.New(rand.NewSource(time.Now().UnixNano())) for i := 0; i < length; i++ { list = append(list,int(r.Intn(1000))) } fmt.Println(list) for i := 1; i < length; i++ { // 利用二分查找,在待排元素左侧找到合适的插入位置 p := suitableIndex(list,i-1,i) // 如果最合适的位置不是待排元素当前位置,那就一次把合适位置后的元素都向后移动一位 if p != i { temp := list[i] for j := i; j > p; j-- { list[j],list[j-1] = list[j-1],list[j] } list[p] = temp } fmt.Println(list) } } func suitableIndex(list []int,start int,end int,current int) int { // 比到最后美的比的时候就去对比下当前位置与待排元素的大小,并返回较大值的位置 if start >= end { if list[start] < list[current] { return current } else { return start } } center := (end-start)/2 + start // 如果中间的元素比较大,就继续向左侧寻找。反之则向右 if list[center] > list[current] { return suitableIndex(list,start,center,current) } else { return suitableIndex(list,center+1,end,current) } } 运行结果 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |