桶排序

基本思想

将要排序的数据放入到几个有序桶中，每个桶里面的数据单独排序，然后把各个同种的数据串起来即完成排序。

算法分析

时间复杂度

最坏: O(nlog₂n)
最好: O(n)
平均: O(n)
因为将n个数据平均分配到m个桶里，每个桶里面的元素有k=n/m个，所以桶内排序使用快排时间复杂度为O(k*log₂k), m个桶时间复杂度为O(m*k*log₂k)，因为k=n/m，所以整个桶排序时间复杂度为O(nlog₂(n/m))，当m接近n时log₂(n/m)是一个非常小的数，所以桶排序时间复杂度为O(n).

空间复杂度

O(m)

稳定性

不稳定

使用场景

条件

数据很容易被分到m个桶，且桶之间存在大小关系.
数据在各个桶之间分布均匀.

场景

外排
按订单金额给订单排序

参考代码

//桶排序+快排
func bucketSortASC(value common.Value) {
    bucket := common.NewBucket(BucketSize)
    bucketSortASCCore(bucket, value, func(va int) int {
        return va / BucketSize
    })
    for _, v := range bucket {
        qSortASC(v)
    }
    value = value[:0]
    for i := 0; i < len(bucket); i++ {
        if va, ok := bucket[i]; ok {
            value = append(value, va...)
        }
    }
}

func bucketSortASCCore(bucket map[int][]int, value common.Value, hashFunc func(int2 int) int) {
    len := value.Len()
    for i := 0; i < len; i++ {
        code := hashFunc(value[i])
        bucket[code] = append(bucket[code], value[i])
    }
}

桶排序