基数排序

排序

说明

从低位到高位稳定地按数字位排序；适用于非负整数，时间 O(d(n+b))。

分析

从个位开始，对每一位进行稳定的计数排序，让低位顺序在处理高位时得以保留。位数固定时可获得接近线性的性能。

图解推演

补充 [21,13,12,22]：个位稳定排序得到 [21,12,22,13]，十位稳定排序得到 [12,13,21,22]。第二轮相同十位的元素保留第一轮的个位顺序，这就是低位排序能够累积到最终结果的原因；任意不稳定的桶内排列会破坏该性质。

查看图表代码

适用前提与边界

示例采用十进制并只处理非负整数；负数或不同类型的键需要额外编码策略。处理完最高有效位后先结束，避免下一次 exp 乘十超出本机 int 范围。

示例输入与调用

a := []int{170, 45, 75, 2}
	RadixSort(a)
	fmt.Println(a)

运行输出

[2 45 75 170]

完整 Go 示例

package main

import "fmt"

func RadixSort(a []int) {
	if len(a) == 0 {
		return
	}
	max := 0
	for _, x := range a {
		if x > max {
			max = x
		}
	}
	out := make([]int, len(a))
	for exp := 1; max/exp > 0; exp *= 10 {
		count := [10]int{}
		for _, x := range a {
			count[x/exp%10]++
		}
		for i := 1; i < 10; i++ {
			count[i] += count[i-1]
		}
		for i := len(a) - 1; i >= 0; i-- {
			d := a[i] / exp % 10
			count[d]--
			out[count[d]] = a[i]
		}
		copy(a, out)
		if exp > max/10 {
			break // 下一位已无数字，同时避免 exp *= 10 溢出。
		}
	}
}

func main() {
	a := []int{170, 45, 75, 2}
	RadixSort(a)
	fmt.Println(a)
}