基数排序(Radix Sort)是一种非比较整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。
从最低有效位(或最高有效位)开始,根据每一位的数字将整数分配到相应的桶中。
按照桶的顺序(0至9)收集桶中的整数。
对整数的每一位重复上述过程。
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]
}
}
基数排序是一种非常特殊的排序算法,它通过多次的按位排序和收集来实现整体的排序。这种方法在处理整数序列时特别有效,特别是当整数的范围相对集中时。
掌握基数排序的原理和代码实现,可以帮助我们理解如何通过非比较的方式对整数进行排序,这在某些特定场景下可能非常有用。