二分挿入ソートは、二分検索を使用して挿入位置を決定する挿入ソートの変形です。アルゴリズムの時間計算量は O(n2) です
アルゴリズムは次のように機能します:
<オル>
バイナリ検索中に、数値が見つからず、インデックスが返されない可能性があります。二分検索の特殊性により、検索された数値に最も近い数値が検索され、インデックスを返すには、そのインデックスを求めた数値と比較する必要があります。求めた数値が小さい場合、求めた数値は次の位置にある必要があります。インデックスが左側にあり、それ以上の場合は右側にあります。
Go コード:
import (
"fmt"
"math/rand"
"time"
)
const numbersCount = 20
const maximalNumber = 100
func binarySearch(numbers []int, item int, low int, high int) int {
for high > low {
center := (low + high) / 2
if numbers[center] < item { low = center + 1 } else if numbers[center] > item {
high = center - 1
} else {
return center
}
}
if numbers[low] < item {
return low + 1
} else {
return low
}
}
func main() {
rand.Seed(time.Now().Unix())
var numbers [numbersCount]int
for i := 0; i < numbersCount; i++ {
numbers[i] = rand.Intn(maximalNumber)
}
fmt.Println(numbers)
for i := 1; i < len(numbers); i++ { searchAreaLastIndex := i - 1 insertNumber := numbers[i] insertIndex := binarySearch(numbers[:], insertNumber, 0, searchAreaLastIndex) for x := searchAreaLastIndex; x >= insertIndex; x-- {
numbers[x+1] = numbers[x]
}
numbers[insertIndex] = insertNumber
}
fmt.Println(numbers)
}
リンク
ソース
https://www.geeksforgeeks.org/binary-insertion-並べ替え/
https://www.youtube.com/watch?v=-OVB5pOZJug
