共计 1124 个字符,预计需要花费 3 分钟才能阅读完成。
概念
桶排序的基本思想是将待排序数据分成一些有序的桶,每个桶里的数据再进行排序,最后将所有的桶中的数据依次取出,构成有序序列。步骤如下:
- 首先,我们需要确定桶的数量和每个桶的范围。这里我们选择桶的数量等于待排序数据的数量,并且每个桶的范围是一个固定的值。
- 接下来,我们需要将待排序数据分配到对应的桶中。
- 然后,对每个桶中的数据进行排序。
- 最后,我们将所有桶中的数据依次取出,构成有序序列。
代码实现
package main
import ("fmt")
func bucketSort(arr []int, bucketSize int) []int {if len(arr) == 0 {return arr}
// 获取最大值和最小值
minVal, maxVal := arr[0], arr[0]
for _, val := range arr {
if val < minVal {minVal = val} else if val > maxVal {maxVal = val}
}
// 计算桶的数量
bucketCount := (maxVal-minVal)/bucketSize + 1
buckets := make([][]int, bucketCount)
// 将数据分配到对应的桶中
for _, val := range arr {index := (val - minVal) / bucketSize
buckets[index] = append(buckets[index], val)
}
// 对每个桶中的数据进行排序
result := make([]int, 0)
for _, bucket := range buckets {if len(bucket) > 0 {if len(bucket) > 1 {bucket = bucketSort(bucket, bucketSize)
}
result = append(result, bucket...)
}
}
return result
}
func main() {arr := []int{5, 3, 1, 7, 9, 4, 6, 8, 2}
fmt.Println("Unsorted array:", arr)
sortedArr := bucketSort(arr, 2)
fmt.Println("Sorted array:", sortedArr)
}
在上面的代码中,我们首先获取待排序数据的最大值和最小值,然后计算桶的数量。接下来,我们将待排序数据分配到对应的桶中,再对每个桶中的数据进行排序。最后,我们将所有桶中的数据依次取出,构成有序序列。
在 bucketSort
函数中,我们首先检查待排序数据是否为空,如果是,则直接返回。然后,我们计算每个桶的范围,并创建相应数量的桶。接下来,我们将待排序数据分配到对应的桶中,再对每个桶中的数据进行排序。最后,我们将排序后的数据添加到结果数组中,并返回结果数组。
正文完
发表至: 算法与数据结构
2023-04-16