基本思想
将整数按位数切割成不同的数字，然后从低位开始，依次到高位，逐位进行排序，从而达到排序的目的。
算法步骤
基数排序算法可以采用「最低位优先法（Least Significant Digit First）」或者「最高位优先法（Most Significant Digit first）」。最常用的是「最低位优先法」。
下面我们以最低位优先法为例，讲解一下算法步骤。
- 确定排序的最大位数：遍历数组元素，获取数组最大值元素，并取得对应位数。
- 从最低位（个位）开始，到最高位为止，逐位对每一位进行排序：
- 定义一个长度为 10的桶数组 buckets，每个桶分别代表 0∼9 中的 1 个数字。
- 按照每个元素当前位上的数字，将元素放入对应数字的桶中。
- 清空原始数组，然后按照桶的顺序依次取出对应元素，重新加入到原始数组中。
以 [692,924,969,503,871,704,542,436]为例，演示一下基数排序算法的整个步骤。
适用场景
大规模整数排序，固定长度数据排序，稳定性要求高的排序场景，数据分布较为均匀的情况，外部排序场景
排序稳定性
基数排序采用的桶排序是稳定的。基数排序是一种 稳定排序算法。
代码实现(golang)
func getMax(arr []int) int {max := arr[0]for _, v := range arr {if v > max {max = v}}return max
}func radixSort(arr []int) []int {max := getMax(arr)exp := 1for max/exp > 0 {buckets := make([][]int, 10)for _, v := range arr {digit := (v / exp) % 10buckets[digit] = append(buckets[digit], v)}arr = []int{}for _, bucket := range buckets {arr = append(arr, bucket...)}exp *= 10}return arr
}func main() {arr := []int{170, 45, 75, 90, 802, 24, 2, 66}sortedArr := radixSort(arr)fmt.Println(sortedArr)
}
