算法：基数排序

运维开发王义杰

发布于 2023-09-26 12:11:06

1790

发布于 2023-09-26 12:11:06

文章被收录于专栏：运维开发王义杰

1. 什么是基数排序？

基数排序（Radix Sort）是一种非比较整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。

2. 基数排序的工作原理

2.1 按位排序

从最低有效位（或最高有效位）开始，根据每一位的数字将整数分配到相应的桶中。

2.2 收集整数

按照桶的顺序（0至9）收集桶中的整数。

2.3 重复过程

对整数的每一位重复上述过程。

3. 基数排序的代码实现



func radixSort(arr []int) []int {
    max := getMax(arr)
    for exp := 1; max/exp > 0; exp *= 10 {
        countingSortByDigit(arr, exp)
    }
    return arr
}

func getMax(arr []int) int {
    max := arr[0]
    for _, value := range arr {
        if value > max {
            max = value
        }
    }
    return max
}

func countingSortByDigit(arr []int, exp int) {
    n := len(arr)
    output := make([]int, n)
    count := make([]int, 10)

    for i := 0; i < n; i++ {
        index := (arr[i] / exp) % 10
        count[index]++
    }

    for i := 1; i < 10; i++ {
        count[i] += count[i-1]
    }

    for i := n - 1; i >= 0; i-- {
        index := (arr[i] / exp) % 10
        output[count[index]-1] = arr[i]
        count[index]--
    }

    for i := 0; i < n; i++ {
        arr[i] = output[i]
    }
}