golang实现简化版桶算法

全栈运维 · · 565 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

/**
 * 简化版桶算法
 *  通过一维数组保存对应数字在一维数组中出现的个数，然后遍历一维数组达到排序的效果
 *  这里一位数组是排序列表的范围，必须10以内的数字列表排序， 则一维数组大小为11 （N+1）
 * 
 * 涉及知识点：
 *   @随机数功能
 *   @时间处理和格式化
 */

package main

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

func main() {

    var scoreList [11]int
    score := [5]int{5, 3, 5, 2, 8}

    for _, v := range score {
        scoreList[v]++
    }

    fmt.Println(scoreList)

    var result []int
    // fmt.Printf("%T, %T\n", result, scoreList)
    // 从小到大
    for i := 1; i <= 10; i++ {
        for j := 1; j <= scoreList[i]; j++ {
            fmt.Println(i, j)
            result = append(result, i)
        }
    }
    fmt.Println(result)

    var result2 []int
    // 从大到小
    for i := 10; i >= 0; i-- {
        for j := 1; j <= scoreList[i]; j++ {
            result2 = append(result2, i)
        }
    }
    fmt.Println(result2)

    fmt.Println("<-------------------------------->")
    // 获取随机数个数
    randCount := 50
    randRandMax := 100
    bucketMax := randRandMax + 1
    // make 创建切片，已经初始化完毕。在append的话，前面值都为0
    // randList := make([]int, randCount)
    var randList []int
    bucket := make([]int, bucketMax)
    seed := rand.New(rand.NewSource(time.Now().UnixNano()))
    for index := 0; index < randCount; index++ {
        number := seed.Intn(randRandMax)
        // fmt.Println(number)
        randList = append(randList, number)
    }
    fmt.Println("原始列表: ", randList)
    for _, v := range randList {
        bucket[v]++
    }
    var result3 []int

    startTime := time.Now()
    for i := randRandMax; i >= 0; i-- {
        for j := 1; j <= bucket[i]; j++ {
            result3 = append(result3, i)
        }
    }
    fmt.Println("排序列表: ", result3)
    duration := time.Since(startTime)
    fmt.Println("耗时：", duration)
}

执行结果：

$ go run demo.go 
[0 0 1 1 0 2 0 0 1 0 0]
2 1
3 1
5 1
5 2
8 1
[2 3 5 5 8]
[8 5 5 3 2]
<-------------------------------->
原始列表:  [80 57 35 27 2 1 87 31 85 96 42 1 82 65 0 16 13 9 40 90 11 38 12 52 40 96 2 7 37 68 75 96 85 34 8 0 95 44 41 34 14 85 87 77 82 33 14 60 37 86]
排序列表:  [96 96 96 95 90 87 87 86 85 85 85 82 82 80 77 75 68 65 60 57 52 44 42 41 40 40 38 37 37 35 34 34 33 31 27 16 14 14 13 12 11 9 8 7 2 2 1 1 0 0]
耗时： 8.834µs

有疑问加站长微信联系（非本文作者）