1、基数 排序 关键点

1、基数排序中，桶的数量应该是定死的，10个桶，每个桶能存储的值也是设置好了的。

• 桶号，是0到9，对应的是数组的下标，或者说map里key的值

• 每个桶存储的值的范围是

  • 每个桶只能存储一个数字，对应的就是桶号，如0号桶，只能存储0

  • 但是个数是没有限制的

2、先将数据按照个位数从小到进行排序；

• 个位数的数字就是对应的桶号，将数值映射到对应的桶里，这样的话，待测试数据就从个位上小到大排序好了，

• 然后将非空桶里的数据重新回写到原数据里

3、再按照十位数进行从小到大排序

• 十位数的数字就是对应的桶号(如果该数值没有十位的话，就默认为0)，将数值映射到对应的桶里，这样的话，待测试数据就从十位上小到大排序好了，

• 然后将非空桶里的数据重新回写到原数据里

4、依次递归2，3步，直到所有的位数全部 排序完了

2、源码

package fangshi2

import (
    "math"
    "fmt"
    "strconv"
)

func RadixSort(data []int) {

    ml := maxLength(data)

    data2Bucket(data, 1, ml)
}

func newBucket() map[int][]int {
    var b = make(map[int][]int)

    for i := 0; i < 10; i++ {
        b[i] = []int{}
    }

    return b
}

func maxLength(data []int) int {
    var ml int
    for _, v := range data {
        t := (int)(math.Log10(float64(v))) + 1
        if ml < t {
            ml = t
        }
    }

    return ml
}

func data2Bucket(data []int, i, ml int) {
    if i > ml {
        return
    }

    sortForBucket(data, i)

    data2Bucket(data, i+1, ml)
}

func sortForBucket(data []int, i int) {
    b := newBucket()

    for _, v := range data {
        vs := strconv.Itoa(v)
        l := len(vs)

        if i <= l {
            vd := fmt.Sprintf("%c", vs[l-i])
            k, e := strconv.Atoi(vd)
            if e == nil {
                b[k] = append(b[k], v)
            }

        } else {
            b[0] = append(b[0], v)
        }
    }

    var index int
    for j:=0; j<10; j++{
        v := b[j]
        if len(v) != 0 {
            for i := 0; i < len(v); i++ {
                data[index] = v[I]
                index++
            }
        }
    }
}

将测试数据映射到桶里，再回写到原数据里

3、测试

package fangshi2

import (
    "testing"
    "fmt"
)


func TestRadixSort(b *testing.T) {
    datas := []int{
        9,8,7,4,5,4,3,3,1,22,23,222,28,77,78,57,25,33,39,34,44,89,22,12,132,321,461,31,30,55,54,66,88,77,66,89,59,69,68,67,63,61,62,67,77,71,72,79,73,77,88,73,11,13,18,12,19,88,78,89,83,84,81,99,92,93,94,98,96,
    }

    //datas := []int{
    //  2,3,4,1,6,8,2,11,32,45,31,
    //}


    RadixSort(datas)

    for _, d := range datas{
        fmt.Printf("%d ", d)
    }
    fmt.Println()
}

基数排序测试

  
  
  
  

打赏