桶排序很适用于有 0~100 个数, 然后打乱顺序, 重新分配. 不过如果给定的数据范围差距很大, 桶排序的算法效率变低.
步骤
- 申请 n 个桶,根据需求
- 遍历一个给定的数组,找到最大值和最小值
- 遍历数组,假设遍历的值为
num,按照公式floor((num - min) / n)即可得知放入哪个桶 - 如果桶中已存在元素,拉出一个链表,并且按照从小到大的顺序
- 重复 3,4 直至把所有元素装入桶中
- 遍历所有桶中的链表, 直接把每一个元素载入数组,排序即可完成
package main
import (
"fmt"
"math"
)
func main() {
data := []int{111, 9, 2, 4, 9, 3, 3, 5, 7, 1, 8, 2, 11, 22, 99, 192}
fmt.Println(BucketSort(data, 4))
}
func BucketSort(data []int, buckets int) []int {
if len(data) == 0 {
return data
}
// find min and max number
min, max := data[0], data[0]
for _, number := range data {
if number < min {
min = number
continue
}
if number > max {
max = number
}
}
bucketChunk := (max - min 1) / buckets
bucketLinks := make([]*LinkList, buckets)
// 把所有数字放入桶中并且排序
for _, number := range data {
// 找到放入的桶中
bucketIndex := int(math.Floor(float64((number - min) / bucketChunk)))
if bucketLinks[bucketIndex] == nil {
bucketLinks[bucketIndex] = &LinkList{}
}
bucketLinks[bucketIndex].put(number)
}
// 再遍历所有桶直接连接
index := 0
sortData := make([]int, len(data))
for _, bucket := range bucketLinks {
if bucket == nil {
continue
}
head := bucket.head
for head != nil {
sortData[index] = head.data
index
head = head.next
}
}
return sortData
}
type LinkList struct {
head *Node
}
type Node struct {
data int
next *Node
}
func (b *LinkList) put(num int) {
if b.head == nil {
b.head = &Node{num, nil}
return
}
if b.head.data > num {
b.head = &Node{num, b.head}
return
}
// 排序插入
head := b.head
for head.next != nil {
if head.next.data > num {
// 连接链表
head.next = &Node{num, head.next};
return
}
head = head.next;
}
head.next = &Node{num, nil}
}
