桶排序

排序

说明

按范围分桶后分别排序；分布较均匀时接近线性。

分析

根据值与最小值的距离把元素放进不同桶，每个桶内部排序后依次连接。效果依赖数据是否均匀分布以及桶宽是否合适。

图解推演

补充 [8,3,1,6]、桶宽 3，以最小值 1 为起点，区间 [1,4)、[4,7)、[7,10) 分别收到 [3,1]、[6]、[8]。桶内排序后顺序拼接得到 [1,3,6,8]。桶宽决定桶数量及桶内工作量，值域很宽而数据很少时不能盲目分配大量空桶。

查看图表代码

适用前提与边界

示例要求 bucketSize 大于零；所有值落入同一桶时优势会消失。

示例输入与调用

fmt.Println(BucketSort([]int{31, 12, 25, 11}, 10))

运行输出

[11 12 25 31]

完整 Go 示例

package main

import (
	"fmt"
	"sort"
)

func BucketSort(a []int, bucketSize int) []int {
	if len(a) == 0 {
		return nil
	}
	min, max := a[0], a[0]
	for _, x := range a {
		if x < min {
			min = x
		}
		if x > max {
			max = x
		}
	}
	buckets := make([][]int, (max-min)/bucketSize+1)
	for _, x := range a {
		i := (x - min) / bucketSize
		buckets[i] = append(buckets[i], x)
	}
	out := make([]int, 0, len(a))
	for _, b := range buckets {
		sort.Ints(b)
		out = append(out, b...)
	}
	return out
}

func main() {
	fmt.Println(BucketSort([]int{31, 12, 25, 11}, 10))
}