在编写基数排序的时候，我还找到一个规律，取一个数的个位十位百位，是经常需要用到的

// 数字，右数第几位，从1开始
func digit(num int, loc int) int {
    return num % int(math.Pow10(loc)) / int(math.Pow10(loc-1))
}

算法描述

• 取得数组中的最大数，并取得位数；
• arr为原始数组，从最低位开始取每个位组成radix数组；
• 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

算法实习

版本一

为了简单起见，我这里用了一个 数组，数组中是一个队列，这样可以方便取到队列头部数据。

func radixsort(arr []int) []int {
    maxValueLen := 0 // 需要循环多少次，以最大数字为准
    for i := 0; i < len(arr); i++ {
        n := len(strconv.Itoa(arr[i])) // 方便起见，数字转字符，再取长度
        if n > maxValueLen {
            maxValueLen = n
        }
    }

    for loc := 1; loc <= maxValueLen; loc++ {
        arr = sort(arr, loc)
    }
    return arr
}

// 数组中每一位都需要排序
func sort(arr []int, loc int) []int {
    bucket := make([]*list.List, 10) // 0~9 总共10个队列
    for i := 0; i <= 9; i++ {
        bucket[i] = list.New()
    }

    for i := 0; i < len(arr); i++ {
        ji := digit(arr[i], loc)    // 获取对应位的数字
        bucket[ji].PushBack(arr[i]) //按数字 将数据 push 进队列
    }

    tempArr := []int{}
    for i := 0; i <= 9; i++ {
        for bucket[i].Len() > 0 { // 队列中不为空
            fv := bucket[i].Front() // 将数据弹出
            tempArr = append(tempArr, fv.Value.(int))
            bucket[i].Remove(fv)
        }
    }
    return tempArr // 将本轮排好序的数据返回
}

// 数字，右数第几位，从1开始
func digit(num int, loc int) int {
    return num % int(math.Pow10(loc)) / int(math.Pow10(loc-1))
}

func TestRadixsort(t *testing.T) {
    arr := []int{1, 2, 12, 4343242, 123, 4, 55, 666, 77, 102, 3249, 21210, 31312}
    t.Log(arr)
    t.Log(radixsort(arr))
}

func BenchmarkRadixsort(b *testing.B) {
    arr := rand.Perm(math.MaxInt16 * 10)
    for i := 0; i < b.N; i++ {
        radixsort(arr)
    }
}

版本二

func radixsort(arr []int) []int {
    maxValueLen := 0 // 需要循环多少次，以最大数字为准
    for i := 0; i < len(arr); i++ {
        n := len(strconv.Itoa(arr[i])) // 方便起见，数字转字符，再取长度
        if n > maxValueLen {
            maxValueLen = n
        }
    }
    for loc := 1; loc <= maxValueLen; loc++ {
        sort(arr, loc)
    }
    return arr
}

func sort(arr []int, loc int) {
    bucket := make([][]int, 10) // 0~9 总共10个队列

    for i := 0; i < len(arr); i++ {
        ji := digit(arr[i], loc) // 获取对应位的数字
        if bucket[ji] == nil {
            bucket[ji] = make([]int, 0) // 如果 bucket 需要再去初始化
        }

        bucket[ji] = append(bucket[ji], arr[i]) // 将数字 push 进去
    }

    idx := 0
    for i := 0; i <= 9; i++ {
        for j := 0; j < len(bucket[i]); j++ {
            // 遍历二维数组
            arr[idx] = bucket[i][j] //将数字取出来 给原数组重新赋值
            idx++
        }
    }
}

// 数字，右数第几位，从1开始
func digit(num int, loc int) int {
    return num % int(math.Pow10(loc)) / int(math.Pow10(loc-1))
}

func TestRadixsort(t *testing.T) {
    arr := []int{1, 2, 12, 4343242, 123, 4, 55, 666, 77, 102, 3249, 21210, 31312}
    t.Log(arr)
    // t.Log(radixsort(arr))
    t.Log(radixsort(arr))
}


func BenchmarkRadixsort(b *testing.B) {
    arr := rand.Perm(math.MaxInt16 * 10)
    for i := 0; i < b.N; i++ {
        radixsort(arr)
    }
}

版本二直接使用了一个二维数组去实现了，后面直接去掉 tempArr，给原数组赋值即可，对各种写法都Benchmark了一下，确实性能提供了很多倍。

小结

基数排序的逻辑可以查看B站，但是他的代码，让我很费解，这边都是自己实现的逻辑，感觉比较好理解。

至此，8大排序均已写完，大学里用 c 和 java 都实现过，这是用 golang 重新实现了。知识这东西时间长了那真是叫似曾相识，理不清楚。