[golang] 数据结构-二分插入排序

发布时间:2020-07-03 05:07:52 作者:NicoChen
来源:网络 阅读:1582

接上文 直接插入排序
直接插入排序每轮比较中,都需要把待处理的元素与前面每一位元素进行比较。那么有没有一种方法可以优化下,减少比较次数呢?答案当然是有的,下面介绍的二分插入就是直接插入排序的优化算法之一。

原理
直接插入排序是挨个的去比较,而二分插入排序则是利用二分搜索的原理,将待排序的元素与左侧已经排好序的队列的中间元素(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)
    }

}

运行结果
[golang] 数据结构-二分插入排序

推荐阅读:
  1. 使用Go Hijack和jQuery轻松实现异步推送服务
  2. go语言如何删除数组元素

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

go 排序算法 二分

上一篇:信息安全系列(2)--信息安全基础

下一篇:spero性能调优记录

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》