接上文 直接插入排序
直接插入排序每輪比較中，都需要把待處理的元素與前面每一位元素進(jìn)行比較。那么有沒有一種方法可以優(yōu)化下，減少比較次數(shù)呢？答案當(dāng)然是有的，下面介紹的二分插入就是直接插入排序的優(yōu)化算法之一。

從網(wǎng)站建設(shè)到定制行業(yè)解決方案，為提供成都做網(wǎng)站、成都網(wǎng)站建設(shè)服務(wù)體系，各種行業(yè)企業(yè)客戶提供網(wǎng)站建設(shè)解決方案，助力業(yè)務(wù)快速發(fā)展。成都創(chuàng)新互聯(lián)公司將不斷加快創(chuàng)新步伐，提供優(yōu)質(zhì)的建站服務(wù)。

原理
直接插入排序是挨個的去比較，而二分插入排序則是利用二分搜索的原理，將待排序的元素與左側(cè)已經(jīng)排好序的隊(duì)列的中間元素(n/2)進(jìn)行比較。較小時則繼續(xù)與中間元素左側(cè)隊(duì)列中間元素進(jìn)行比較，較大則與中間元素右側(cè)隊(duì)列的中間元素進(jìn)行比較，直至找到合適的位置，再講這個位置后續(xù)的元素向后移動一位，帶插入的元素放到這個合適的位置，從而完成一輪排序。

復(fù)雜度
平均時間復(fù)雜度為O(n^2)，空間復(fù)雜度始終為1。最佳情況時，僅需進(jìn)行n-1次比較，無需交換。
因?yàn)椴粫嗤瑪?shù)值元素的先后順序，所以它也是一種穩(wěn)定排序。

代碼實(shí)現(xiàn)

package main

import (
    "fmt"
    "math/rand"
    "time"
)

func main() {
    var length = 10
    var list []int

    // 以時間戳為種子生成隨機(jī)數(shù)，保證每次運(yùn)行數(shù)據(jù)不重復(fù)
    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++ {
        // 利用二分查找，在待排元素左側(cè)找到合適的插入位置
        p := suitableIndex(list, 0, i-1, i)

        // 如果最合適的位置不是待排元素當(dāng)前位置，那就一次把合適位置后的元素都向后移動一位
        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 {
    // 比到最后美的比的時候就去對比下當(dāng)前位置與待排元素的大小，并返回較大值的位置
    if start >= end {
        if list[start] < list[current] {
            return current
        } else {
            return start
        }
    }

    center := (end-start)/2 + start

    // 如果中間的元素比較大，就繼續(xù)向左側(cè)尋找。反之則向右
    if list[center] > list[current] {
        return suitableIndex(list, start, center, current)
    } else {
        return suitableIndex(list, center+1, end, current)
    }

}

運(yùn)行結(jié)果

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務(wù)器買多久送多久。

本文名稱：[golang]數(shù)據(jù)結(jié)構(gòu)-二分插入排序-創(chuàng)新互聯(lián)
文章位置：http://www.chinadenli.net/article42/gchhc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供用戶體驗(yàn)、搜索引擎優(yōu)化、網(wǎng)站維護(hù)、小程序開發(fā)、ChatGPT、網(wǎng)站策劃

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)