如何基于归并排序实现面试调度器并保留键值对应关系？

你之前的错误在于两点：一是把整个int数组直接传入switch判断（switch只能匹配单个值，无法处理数组）；二是将应聘者的姓名和分数拆分处理，导致排序后没法保留两者的关联关系。

正确的思路是不要拆分键值对，把应聘者的姓名和分数封装成一个完整的实体，排序时直接对实体数组进行MergeSort，这样就能始终保证姓名和分数的对应关系。

步骤1：定义应聘者实体类 #

先创建一个类来存储每个应聘者的姓名和分数，确保两者绑定：

public class Applicant
{
    public string Name { get; set; }
    public int Score { get; set; }

    public Applicant(string name, int score)
    {
        Name = name;
        Score = score;
    }
}

步骤2：实现针对实体的MergeSort算法 #

修改MergeSort逻辑，让它根据Applicant的Score属性进行降序排序：

public static void MergeSort(Applicant[] arr)
{
    if (arr.Length <= 1)
        return;

    int mid = arr.Length / 2;
    Applicant[] left = new Applicant[mid];
    Applicant[] right = arr.Length % 2 == 0 ? new Applicant[mid] : new Applicant[mid + 1];

    // 填充左右子数组
    for (int i = 0; i < mid; i++)
        left[i] = arr[i];
    for (int i = 0; i < right.Length; i++)
        right[i] = arr[i + mid];

    // 递归排序左右子数组
    MergeSort(left);
    MergeSort(right);

    // 合并两个有序数组
    Merge(arr, left, right);
}

private static void Merge(Applicant[] arr, Applicant[] left, Applicant[] right)
{
    int leftIdx = 0, rightIdx = 0, arrIdx = 0;

    // 按分数降序合并
    while (leftIdx < left.Length && rightIdx < right.Length)
    {
        if (left[leftIdx].Score >= right[rightIdx].Score)
        {
            arr[arrIdx] = left[leftIdx];
            leftIdx++;
        }
        else
        {
            arr[arrIdx] = right[rightIdx];
            rightIdx++;
        }
        arrIdx++;
    }

    // 处理剩余未合并的元素
    while (leftIdx < left.Length)
    {
        arr[arrIdx] = left[leftIdx];
        leftIdx++;
        arrIdx++;
    }
    while (rightIdx < right.Length)
    {
        arr[arrIdx] = right[rightIdx];
        rightIdx++;
        arrIdx++;
    }
}

步骤3：实际使用示例 #

把原有的键值对数据转换成实体数组，排序后直接按顺序调度即可：

// 假设原数据存储在Dictionary中
Dictionary<string, int> applicantDict = new Dictionary<string, int>()
{
    {"张三", 88},
    {"李四", 95},
    {"王五", 79},
    {"赵六", 92}
};

// 转换为Applicant数组
Applicant[] applicantArray = applicantDict.Select(kv => new Applicant(kv.Key, kv.Value)).ToArray();

// 执行MergeSort排序
MergeSort(applicantArray);

// 按排序后的顺序呼叫应聘者
foreach (var applicant in applicantArray)
{
    Console.WriteLine($"呼叫应聘者：{applicant.Name}，分数：{applicant.Score}");
}

为什么之前的方法不可行 #

单独提取分数数组排序后，手动用switch匹配分数关联姓名的方式，不仅代码冗余，而且遇到分数相同的应聘者时，根本无法区分对应哪个姓名，完全破坏了数据的关联性。而封装成实体后，排序操作针对的是完整的应聘者对象，姓名和分数始终绑定，从根源上解决了关联丢失的问题。

内容的提问来源于stack exchange，提问作者Jeyson