基数排序是根据数字每一位从低到高去进行分类排序的
比如对于数组[1, 11, 2, 12],从个位数开始,1和11分到了桶1,2和12分到了桶二,接着十位数,1和2分到了一桶,但由于在上一次分桶中,2在1之后,所以这个顺序仍然会保留,11和12也是一样,因此最后得到正确的有序数组[1, 2, 11, 12]
func digit(num, exp int) int {
return (num / exp) % 10
}
func countingSortDigit(nums []int, exp int) {
counter := make([]int, 10)
n := len(nums)
// 统计0~9数字出现次数
for i := 0; i < n; i++ {
d := digit(nums[i], exp)
counter[d]++
}
// 计算出现次数的前缀和,以方便计算后面元素所放置位置
for i := 1; i < 10; i++ {
counter[i] += counter[i-1]
}
// 根据数字找到所在的桶
res := make([]int, n)
for i := n - 1; i >= 0; i-- {
d := digit(nums[i], exp)
j := counter[d] - 1
res[j] = nums[i]
// 减去前缀和,保证该位同数字不落入同一个位置
counter[d]--
}
for i := 0; i < n; i++ {
nums[i] = res[i]
}
}
func radixSort(nums []int) {
// 找到数组中最大的数
x := math.MinInt
for _, num := range nums {
if num > x {
x = num
}
}
// 从低到高位进行排序
for exp := 1; exp <= x; exp *= 10 {
countingSortDigit(nums, exp)
}
}
Ref
- https://www.hello-algo.com/chapter_sorting/radix_sort