C#实现多关键字排序（基于基数排序的高效稳定排序教程）

多关键字排序原理

多关键字排序是指对记录按照多个字段依次排序。例如：学生信息包含（班级, 学号），我们希望先按班级升序，班级相同时再按学号升序。

关键技巧：从最次要关键字开始排序，逐步到主要关键字。因为基数排序是稳定的，后一次排序不会打乱前一次相同关键字的顺序。

举个例子：要按 (Key1, Key2) 排序，其中 Key1 是主关键字，Key2 是次关键字。我们应该：
1. 先按 Key2 排序
2. 再按 Key1 排序
最终结果就是按 Key1 主排序，Key1 相同时按 Key2 排序。

C# 实现多关键字基数排序

下面我们用 C# 实现一个支持两个整数关键字的多关键字排序。假设我们有一个结构体 Record，包含 Primary（主关键字）和 Secondary（次关键字）。

using System;using System.Collections.Generic;public struct Record{    public int Primary;   // 主关键字    public int Secondary; // 次关键字    public override string ToString()    {        return $"({Primary}, {Secondary})";    }}public class MultiKeyRadixSort{    // 对 records 按照 (Primary, Secondary) 进行多关键字排序    public static void Sort(List<Record> records)    {        if (records == null || records.Count <= 1) return;        // 第一步：按次要关键字（Secondary）排序        RadixSortBy(records, r => r.Secondary);        // 第二步：按主要关键字（Primary）排序        RadixSortBy(records, r => r.Primary);    }    // 基数排序辅助方法：根据指定的键函数排序    private static void RadixSortBy(List<Record> records, Func<Record, int> keySelector)    {        // 获取最大值以确定位数        int maxValue = 0;        foreach (var r in records)        {            int key = keySelector(r);            if (key < 0)                throw new ArgumentException("基数排序暂不支持负数");            if (key > maxValue) maxValue = key;        }        // 对每一位进行计数排序        for (int exp = 1; maxValue / exp > 0; exp *= 10)        {            CountingSortByDigit(records, exp, keySelector);        }    }    // 按某一位数字进行计数排序    private static void CountingSortByDigit(        List<Record> records,        int digitPlace,        Func<Record, int> keySelector)    {        int n = records.Count;        var output = new Record[n];        var count = new int[10]; // 基数为10（0-9）        // 统计当前位上各数字出现次数        foreach (var r in records)        {            int digit = (keySelector(r) / digitPlace) % 10;            count[digit]++;        }        // 转换为累积计数        for (int i = 1; i < 10; i++)        {            count[i] += count[i - 1];        }        // 从后往前构建输出数组（保证稳定性）        for (int i = n - 1; i >= 0; i--)        {            int digit = (keySelector(records[i]) / digitPlace) % 10;            output[count[digit] - 1] = records[i];            count[digit]--;        }        // 复制回原数组        for (int i = 0; i < n; i++)        {            records[i] = output[i];        }    }}

使用示例

class Program{    static void Main()    {        var data = new List<Record>        {            new Record { Primary = 2, Secondary = 5 },            new Record { Primary = 1, Secondary = 3 },            new Record { Primary = 2, Secondary = 1 },            new Record { Primary = 1, Secondary = 7 },            new Record { Primary = 3, Secondary = 2 }        };        Console.WriteLine("排序前:");        data.ForEach(r => Console.WriteLine(r));        MultiKeyRadixSort.Sort(data);        Console.WriteLine("\n排序后（按 Primary 升序，Primary 相同则按 Secondary 升序）:");        data.ForEach(r => Console.WriteLine(r));    }}

输出结果：

排序前:(2, 5)(1, 3)(2, 1)(1, 7)(3, 2)排序后（按 Primary 升序，Primary 相同则按 Secondary 升序）:(1, 3)(1, 7)(2, 1)(2, 5)(3, 2)

注意事项与扩展

• 本实现仅支持非负整数关键字。若需支持负数，可先做偏移处理。
• 若关键字不是整数（如字符串），可将其转换为数字序列再应用基数排序。
• 对于更多关键字（如三个以上），只需按从次到主的顺序依次调用 RadixSortBy 即可。
• 该算法是典型的稳定排序算法，适用于对排序稳定性有要求的场景。

总结

通过本文，你已经掌握了如何在 C# 中利用基数排序实现高效的多关键字排序。这种方法不仅性能优越（接近线性时间），而且代码清晰、逻辑严谨。无论你是初学者还是进阶开发者，掌握这种稳定排序算法都将大大提升你的编程能力。

赶快动手试试吧！你可以将此方法应用于学生成绩排序、日志分析、数据库索引优化等实际场景中。