接上文 直接插入排序
直接插入排序每轮比较中,都需要把待处理的元素与前面每一位元素进行比较。那么有没有一种方法可以优化下,减少比较次数呢?答案当然是有的,下面介绍的二分插入就是直接插入排序的优化算法之一。
原理
直接插入排序是挨个的去比较,而二分插入排序则是利用二分搜索的原理,将待排序的元素与左侧已经排好序的队列的中间元素(n/2)进行比较。较小时则继续与中间元素左侧队列中间元素进行比较,较大则与中间元素右侧队列的中间元素进行比较,直至找到合适的位置,再讲这个位置后续的元素向后移动一位,带插入的元素放到这个合适的位置,从而完成一轮排序。
复杂度
平均时间复杂度为O(n^2),空间复杂度始终为1。最佳情况时,仅需进行n-1次比较,无需交换。
因为不会相同数值元素的先后顺序,所以它也是一种稳定排序。
代码实现
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, 0, 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)
}
}
运行结果
创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。
本文名称:[golang]数据结构-二分插入排序-创新互联
文章位置:https://www.cdcxhl.com/article42/gchhc.html
成都网站建设公司_创新互联,为您提供用户体验、搜索引擎优化、网站维护、小程序开发、ChatGPT、网站策划
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联