Golang 桶排序
最后修改于 2025 年 3 月 9 日
本教程深入探讨 Golang 中的桶排序算法。我们将探索升序和降序排列数字和文本，并使用基准测试将其与快速排序进行比较。
算法 是解决问题或完成任务的一组结构化步骤。它是编程和计算机科学的基石。
排序 将数据组织成特定的序列，例如升序或降序。这对于程序中高效的数据处理和分析至关重要。
常用排序算法
以下是一些流行的排序算法
- 气泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- 桶排序
桶排序算法
桶排序是一种基于分布的排序方法。它将元素分成“桶”，对每个桶进行单独排序，然后将它们合并。当数据在范围内均匀分布时，它表现出色。
与基于比较的排序不同，它依赖于数据分布，因此对于均匀分布来说速度很快，但否则效果较差。
桶排序示例：数值数据
这是 Golang 中用于升序排列数字的桶排序实现。
bucket_sort_numeric.go
package main
import (
"fmt"
"sort"
)
func bucketSort(arr []float64) []float64 {
if len(arr) == 0 {
return arr
}
maxVal := arr[0]
for _, val := range arr {
if val > maxVal {
maxVal = val
}
}
bucketSize := maxVal / float64(len(arr))
buckets := make([][]float64, len(arr))
for i := range buckets {
buckets[i] = []float64{}
}
for _, num := range arr {
idx := int(num / bucketSize)
if idx >= len(arr) {
idx = len(arr) - 1
}
buckets[idx] = append(buckets[idx], num)
}
for i := range buckets {
sort.Float64s(buckets[i])
}
result := []float64{}
for _, bucket := range buckets {
result = append(result, bucket...)
}
return result
}
func main() {
arr := []float64{0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51}
sorted := bucketSort(arr)
fmt.Println("Sorted array:", sorted)
}
这使用桶排序对浮点数切片进行排序。它使用 Go 的 sort.Float64s 对每个桶进行排序。
$ go run bucket_sort_numeric.go Sorted array: [0.32 0.33 0.37 0.42 0.47 0.51 0.52]
桶排序示例：文本数据
这是一个使用桶排序以降序排列字符串的长度的示例。
bucket_sort_textual.go
package main
import (
"fmt"
"sort"
)
func bucketSortTextual(arr []string) []string {
if len(arr) == 0 {
return arr
}
maxLen := 0
for _, s := range arr {
if len(s) > maxLen {
maxLen = len(s)
}
}
buckets := make([][]string, maxLen+1)
for i := range buckets {
buckets[i] = []string{}
}
for _, s := range arr {
buckets[len(s)] = append(buckets[len(s)], s)
}
for i := range buckets {
sort.Sort(sort.Reverse(sort.StringSlice(buckets[i])))
}
result := []string{}
for i := len(buckets) - 1; i >= 0; i-- {
result = append(result, buckets[i]...)
}
return result
}
func main() {
arr := []string{"apple", "banana", "kiwi", "mango", "pear"}
sorted := bucketSortTextual(arr)
fmt.Println("Sorted array:", sorted)
}
这会根据长度以降序排列字符串，在每个桶内按字母顺序反向排序，使用 sort.Reverse。
$ go run bucket_sort_textual.go Sorted array: [banana mango apple pear kiwi]
桶排序与快速排序的比较
桶排序在均匀分布的数据上表现出色，时间复杂度为 O(n + k)，其中 k 是桶的数量。快速排序的平均时间复杂度为 O(n log n)，对于一般情况更具通用性。
基准测试示例
这比较了桶排序和快速排序在大型数据集上的性能。
benchmark.go
package main
import (
"fmt"
"math/rand"
"sort"
"time"
)
func bucketSort(arr []float64) []float64 {
if len(arr) == 0 {
return arr
}
maxVal := arr[0]
for _, val := range arr {
if val > maxVal {
maxVal = val
}
}
bucketSize := maxVal / float64(len(arr))
buckets := make([][]float64, len(arr))
for i := range buckets {
buckets[i] = []float64{}
}
for _, num := range arr {
idx := int(num / bucketSize)
if idx >= len(arr) {
idx = len(arr) - 1
}
buckets[idx] = append(buckets[idx], num)
}
for i := range buckets {
sort.Float64s(buckets[i])
}
result := []float64{}
for _, bucket := range buckets {
result = append(result, bucket...)
}
return result
}
func quickSort(arr []float64) []float64 {
if len(arr) <= 1 {
return arr
}
pivot := arr[len(arr)/2]
left, middle, right := []float64{}, []float64{}, []float64{}
for _, x := range arr {
if x < pivot {
left = append(left, x)
} else if x == pivot {
middle = append(middle, x)
} else {
right = append(right, x)
}
}
return append(append(quickSort(left), middle...), quickSort(right)...)
}
func main() {
rand.Seed(time.Now().UnixNano())
arr := make([]float64, 10000)
for i := range arr {
arr[i] = rand.Float64() * 1000
}
start := time.Now()
bucketSort(append([]float64{}, arr...))
fmt.Printf("Bucket Sort Time: %.6f seconds\n", time.Since(start).Seconds())
start = time.Now()
quickSort(append([]float64{}, arr...))
fmt.Printf("Quick Sort Time: %.6f seconds\n", time.Since(start).Seconds())
}
这将在 10,000 个随机浮点数上对这两种算法进行基准测试。桶排序在均匀数据上可能会略胜一筹，但快速排序的整体一致性更好。
来源
我们已经涵盖了 Golang 中的桶排序，并将其与快速排序进行了比较。它非常适合均匀数据，而快速排序是一种健壮的通用选择。