桶排序很适用于有 0~100 个数, 然后打乱顺序, 重新分配. 不过如果给定的数据范围差距很大, 桶排序的算法效率变低.
步骤
- 申请 n 个桶,根据需求
- 遍历一个给定的数组,找到最大值和最小值
- 遍历数组,假设遍历的值为
num,按照公式floor((num - min) / n)即可得知放入哪个桶 - 如果桶中已存在元素,拉出一个链表,并且按照从小到大的顺序
- 重复 3,4 直至把所有元素装入桶中
- 遍历所有桶中的链表, 直接把每一个元素载入数组,排序即可完成
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
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} } |
最后附上一张动态图展示,来源见水印中.
