[golang] 數據結構-二分插入排序

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

原理
直接插入排序是挨個的去比較，而二分插入排序則是利用二分搜索的原理，將待排序的元素與左側已經排好序的隊列的中間元素(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)
    }

}

運行結果