Go语言实现基数排序：深入理解多关键字排序（从零开始掌握高效稳定排序算法）

什么是基数排序？

基数排序不通过元素之间的比较来排序，而是将整数按位数切割成不同的数字，然后按每个位数分别比较。通常从最低有效位（LSD, Least Significant Digit）开始处理，利用计数排序作为子过程来对每一位进行排序。

它的核心优势是：时间复杂度为 O(d*(n+k))，其中 d 是最大数的位数，n 是元素个数，k 是基数（如10进制则k=10）。对于固定位数的数据，它几乎是线性时间！

多关键字排序是什么意思？

在实际开发中，我们经常需要对结构体数组排序。例如，一个学生列表可能需要先按“班级”排序，班级相同时再按“学号”排序。这里的“班级”和“学号”就是两个关键字，且有优先级之分。

使用基数排序处理多关键字的关键在于：从最低优先级关键字开始排序，逐步向最高优先级推进。因为基数排序是稳定排序，先前的排序结果在后续排序中不会被破坏。

Go语言实现多关键字基数排序

假设我们有一个学生结构体：

type Student struct {    Class int // 班级    ID    int // 学号    Name  string}

我们的目标是：先按 Class 升序，Class 相同时按 ID 升序。

由于基数排序适合处理整数，我们将分别对 Class 和 ID 进行 LSD 基数排序，先排 ID（低优先级），再排 Class（高优先级）。

步骤 1：实现单关键字的基数排序函数

func radixSortByKey(students []Student, keyFunc func(Student) int) {    if len(students) == 0 {        return    }    // 获取最大值以确定位数    maxValue := keyFunc(students[0])    for _, s := range students {        val := keyFunc(s)        if val > maxValue {            maxValue = val        }    }    // 对每一位进行计数排序    for exp := 1; maxValue/exp > 0; exp *= 10 {        countingSortByDigit(students, exp, keyFunc)    }}// 按指定位（exp 表示 1, 10, 100...）进行计数排序func countingSortByDigit(students []Student, exp int, keyFunc func(Student) int) {    n := len(students)    output := make([]Student, n)    count := make([]int, 10) // 基数为10（0-9）    // 统计当前位上各数字出现次数    for _, s := range students {        digit := (keyFunc(s) / exp) % 10        count[digit]++    }    // 转换为累积计数（确定位置）    for i := 1; i < 10; i++ {        count[i] += count[i-1]    }    // 从后往前构建输出数组（保证稳定性）    for i := n - 1; i >= 0; i-- {        digit := (keyFunc(students[i]) / exp) % 10        output[count[digit]-1] = students[i]        count[digit]--    }    // 复制回原数组    copy(students, output)}

步骤 2：组合多关键字排序

记住：**先排低优先级关键字，再排高优先级关键字**！

func multiKeyRadixSort(students []Student) {    // 第一步：按学号（ID）排序 —— 低优先级    radixSortByKey(students, func(s Student) int { return s.ID })    // 第二步：按班级（Class）排序 —— 高优先级    radixSortByKey(students, func(s Student) int { return s.Class })}

完整示例与测试

package mainimport "fmt"type Student struct {    Class int    ID    int    Name  string}func main() {    students := []Student{        {Class: 2, ID: 103, Name: "Alice"},        {Class: 1, ID: 102, Name: "Bob"},        {Class: 2, ID: 101, Name: "Charlie"},        {Class: 1, ID: 101, Name: "David"},    }    fmt.Println("排序前:")    for _, s := range students {        fmt.Printf("%+v\n", s)    }    multiKeyRadixSort(students)    fmt.Println("\n排序后（先Class升序，再ID升序）:")    for _, s := range students {        fmt.Printf("%+v\n", s)    }}

运行结果：

排序前:{Class:2 ID:103 Name:Alice}{Class:1 ID:102 Name:Bob}{Class:2 ID:101 Name:Charlie}{Class:1 ID:101 Name:David}排序后（先Class升序，再ID升序）:{Class:1 ID:101 Name:David}{Class:1 ID:102 Name:Bob}{Class:2 ID:101 Name:Charlie}{Class:2 ID:103 Name:Alice}

注意事项与适用场景

• 基数排序仅适用于整数或可映射为整数的关键字。
• 必须是稳定排序，否则多关键字排序会失效。
• 当数据范围较大但位数较少时（如IP地址、固定长度ID），效率极高。
• 不适合浮点数或字符串直接排序（需特殊处理）。

总结

通过本教程，你已经掌握了如何在 Go语言 中实现支持 多关键字排序 的 基数排序算法。这种技术在处理结构化数据（如日志、用户信息、成绩表）时非常实用。记住排序顺序：从最低优先级到最高优先级，利用基数排序的稳定性，即可轻松实现复杂的排序需求。

希望这篇 Go排序教程 对你有所帮助！动手试试吧，编程能力就是在实践中提升的！