基数排序(Radix Sort)是一种非比较排序算法，它通过将数据按位数切割成不同的数字来进行排序。基数排序有两种排序方式，一种是最高位优先(Most Siqnificant Digit, MSD)，另一种是最低位优先(LeastSignificant Digit, LsD)。
当我们说基数排序的高位优先(MSD)时，我们是指从最高位(或称为“最显著的位”)开始排序。这种方法的优点是它可以在第一次分配后就得到大量有序的数据段，这可以使得后续的排序更加高效。但是，如果数据在最高位分布不均匀，那么排序可能会涉及大量的递归调用，影响效率。
假设我们有以下数组:[170,45,75,90,802,24,2,66]。
1、最大数的位数是3(802)，所以我们从百位开始排序。
2、对于百位，我们可以创建10个桶(0-9)。在这个例子中，只有桶0、2、4、7、8有数据，因为数组中数字的百位只有这些数字。
3、对每个桶中的数据进行排序(在这个例子中，每个桶中只有一个数据，所以不需要排序)
4、收集数据，得到新的数组:[2,24,45,66,75,90,170,802]。
5、对下一位(十位)进行排序，重复步骤2-4。
6、对个位进行排序，重复步骤2-4。
最后得到的排序数组是:[2,24,45,66,75,90,170,802]。
package main
import (
"fmt"
"math"
)
// getMaxNumber 找到数组中的最大值
func getMaxNumber(arr []int) int {
maxNum := arr[0]
for _, num := range arr {
if num > maxNum {
maxNum = num
}
}
return maxNum
}
// countingSort 是基数排序中用于按照某个位数排序的辅助函数
func countingSort(arr []int, exp int) {
n := len(arr)
output := make([]int, n)
count := make([]int, 10)
// 初始化计数数组
for i := 0; i < 10; i++ {
count[i] = 0
}
// 计算每个元素的频率
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]
}
}
// radixSort 基数排序函数，按高位优先排序
func radixSort(arr []int) []int {
maxNum := getMaxNumber(arr)
exp := 1
for maxNum/exp > 0 {
countingSort(arr, exp)
exp *= 10
}
return arr
}
func main() {
arr := []int{121, 432, 564, 23, 1, 45, 788}
fmt.Println("Original array:", arr)
sortedArr := radixSort(arr)
fmt.Println("Sorted array:", sortedArr)
}
在这个代码中，radixSort 函数首先找到数组中的最大值，然后根据最大值的位数从最低位开始，对数组进行多次计数排序(countingSort)。countingSort函数负责根据当前的位数(由exp变量表示)对数组进行排序。exp 从1开始，每次循环乘以 10，以移动到下一个更高位。这个过程持续到处理完最大数的所有位数。
在这个实现基数排序高位优先示例中的radixSort函数直接修改了传入的数组，并返回了修改后的数组。在实际应用中，如果需要保留原始数组，可以先复制一份再进行排序，
这个实现基数排序高位优先代码示例在main函数中创建了一个整数数组，并调用radixSort函数对其进行排序，然后打印排序前后的数组。