桶排序 Go语言实现经典算法


桶排序原理

桶排序 (Bucket sort)或所谓的箱排序的原理是将数组分到有限数量的桶子里,然后对每个桶子再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序),最后将各个桶中的数据有序的合并起来。
桶排序原理图

效率

桶排序是常见排序里最快的一种,大部分情况下比快排还要快。
时间复杂度为O(N+K),空间复杂度也为O(N+K)

稳定性

桶排序是稳定排序

桶排序的Go语言实现代码

package main

import (
    "fmt"
    "time"
    "math/rand"
)

func bucketSort(numArr []int,bucketSize int){

    minValue := numArr[0]
    maxValue := numArr[0]

    for i := 0; i<len(numArr); i++ {
        if minValue > numArr[i] {
            minValue = numArr[i]
        }
        if maxValue < numArr[i] {
            maxValue = numArr[i]
        }
    }

    // 桶切片初始化
    bucketCount := make([][]int,(maxValue - minValue) / bucketSize +1)

    // 数据入桶
    for i := 0; i<len(numArr); i++ {
        bucketCount[(numArr[i] - minValue) / bucketSize] = append(bucketCount[(numArr[i] - minValue) / bucketSize] , numArr[i])
    }

    key := 0
    // 对每个桶进行排序,这里使用冒泡排序
    for _ , bucket := range bucketCount {
        if (len(bucket) <= 0) { continue; }
        insertionSort(bucket);
        for _ , value := range bucket {
            numArr[key] = value
            key = key+1
        }
    }
    return
}

func insertionSort(numArr []int){
    for i := 0; i < len(numArr); i++ {
        for j := 0; j < len(numArr)-1; j++ {
            if numArr[j] > numArr[j+1]{
                numArr[j],numArr[j+1] = numArr[j+1],numArr[j]
            }
        }
    }
}

// 桶排序
func main(){
    numArr := make([]int,10)
    rand.Seed(time.Now().UnixNano())

    for i:=0; i<len(numArr); i++ {
        numArr[i]=rand.Intn(100)
    }
    fmt.Println(numArr)
    bucketSort(numArr,10)
    fmt.Println(numArr)
}

本文发表于2019年12月17日 23:32
阅读 3868 讨论 0 喜欢 0

抢先体验

扫码体验
趣味小程序
文字表情生成器

闪念胶囊

你要过得好哇,这样我才能恨你啊,你要是过得不好,我都不知道该恨你还是拥抱你啊。

直抵黄龙府,与诸君痛饮尔。

那时陪伴我的人啊,你们如今在何方。

不出意外的话,我们再也不会见了,祝你前程似锦。

这世界真好,吃野东西也要留出这条命来看看

快捷链接
网站地图
提交友链
Copyright © 2016 - 2021 Cion.
All Rights Reserved.
京ICP备2021004668号-1