二分插入排序是插入排序的一种变体，其中使用二分查找来确定插入位置。该算法的时间复杂度为O(n2)
该算法的工作原理如下：
- 循环从零开始到列表末尾
- 在循环中选择一个数字进行排序，该数字存储在单独的变量中
- 二分查找查找索引以将此数字插入左侧的数字
- 一旦找到索引，左侧的数字就会从插入索引开始向右移动一位。在此过程中，需要排序的数字将被删除。
- 之前保存的号码将插入到插入索引处
- 循环结束时，整个列表将被排序
在二分查找过程中，有可能找不到该数字并且不会返回索引。由于二分查找的特殊性，会找到与要查找的数字最接近的数字，然后要返回索引，需要将其与要查找的数字进行比较，如果要查找的数字较小，则要返回的索引应为左侧的索引，如果大于或等于右侧的索引。
执行代码：
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
