在golang中有一些关于桶排序的代码。
然而，我遇到了一个关于index out of range [10]的恐慌，长度为10。
我发现bucketIdx := int((v - minValue) / bucketSize)有一些问题。因为(v - minValue) / bucketSize应该是9.999999999。但是，int((v - minValue) / bucketSize)等于10。我是一个新的学习者在戈兰。我不知道怎么解决。
你可以在这里运行这些代码demo
这是源代码。
package main
import "fmt"
func bucketSort(array []float64) []float64 {
// Determine minimum and maximum values
minValue, maxValue := array[0], array[0]
for _, v := range array {
if v < minValue {
minValue = v
} else if v > maxValue {
maxValue = v
}
}
// Initialize buckets
bucketSize := (maxValue - minValue) / 10
bucketCount := 10
buckets := make([][]float64, bucketCount)
// Distribute elements into buckets
for _, v := range array {
bucketIdx := int((v - minValue) / bucketSize)
buckets[bucketIdx] = append(buckets[bucketIdx], v)
}
// Sort buckets and place back into input array
i := 0
for _, bucket := range buckets {
insertionSort(bucket)
for _, v := range bucket {
array[i] = v
i++
}
}
return array
}
func insertionSort(array []float64) {
n := len(array)
for i := 1; i < n; i++ {
value := array[i]
j := i - 1
for j >= 0 && array[j] > value {
array[j+1] = array[j]
j--
}
array[j+1] = value
}
}
func main() {
array := []float64{0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434}
fmt.Println("Sorted Array: ", bucketSort(array))
}感谢您的时间和考虑。
实际上，我已经尝试过用math.Floor（）来解决这个问题。但它还是不跑。
1条答案
按热度按时间kr98yfug1#
在数学上，
bucketSize := (maxValue - minValue) / 10，(v - minValue) / bucketSize生成值[0...10]。（包括两端）要生成值[0.10）（注意
)表示非包含性），需要进行不同的计算。考虑到我们使用的是浮点数，边缘情况值得考虑。上面提到的[0……10]可能真的是[略小于0……稍大于10]，给出了浮点数学的有限精度及其各种舍入模式。
为了避免特殊的边缘情况处理，而不是
bucketSize1/10的范围，考虑1/(n-1)或1/9。然后将索引计算移动0.5。平均而言，它确实使末端桶的填充量是中间桶的一半，但我们不需要特殊的边缘测试。
当然，你也可以选择安全的方法：
如果
(maxValue - minValue) / n的任何部分溢出或下溢，则需要额外考虑。