排序算法之：比较器排序（Comparator-Based Sorting）的进阶应用：多关键字排序

题目描述
给定一个包含员工信息的数组，每个员工有姓名（字符串）、部门（字符串）和入职年份（整数）三个属性。要求实现一个排序算法，按照以下优先级对员工进行排序：

1. 主要关键字：部门（按字典序升序）
2. 次要关键字：入职年份（按升序排列）
3. 第三关键字：姓名（按字典序升序）
   若两个员工的部门、入职年份和姓名均相同，则其相对顺序保持不变（稳定排序）。

解题过程

1. 理解多关键字排序

   • 多关键字排序需依次比较关键字的优先级。先比较最高优先级的关键字，若相等则比较次高优先级的关键字，依此类推。
   • 例如：比较员工A和B时，先比较部门，若部门不同则按部门排序；若部门相同，再比较入职年份；若年份仍相同，最后比较姓名。

2. 设计比较逻辑

   • 实现一个自定义比较函数（Comparator），定义如下规则：
     • 若部门不同，返回部门的比较结果（升序）。
     • 若部门相同但入职年份不同，返回年份的比较结果（升序）。
     • 若部门和年份均相同，返回姓名的比较结果（升序）。
   • 伪代码示例：

     function compare(employeeA, employeeB):  
       if employeeA.department != employeeB.department:  
         return compare(employeeA.department, employeeB.department)  
       else if employeeA.year != employeeB.year:  
         return employeeA.year - employeeB.year  
       else:  
         return compare(employeeA.name, employeeB.name)  
     

3. 选择排序算法

   • 由于题目要求稳定排序（相同元素保持原顺序），需选择稳定排序算法（如归并排序、插入排序等）。
   • 若使用非稳定排序（如快速排序），可能破坏相同元素的相对顺序。

4. 实现步骤（以归并排序为例）

   • 步骤1：将员工数组平均分成两半，递归地对左右两半进行排序。
   • 步骤2：合并两个已排序的子数组。合并时，使用自定义比较函数决定元素顺序：
     • 比较两个子数组当前首元素的部门、年份、姓名。
     • 将较小的元素放入结果数组，移动对应子数组的指针。
   • 步骤3：递归终止条件为子数组长度为1（已有序）。

5. 复杂度分析

   • 时间复杂度：归并排序为O(n log n)，比较操作的时间复杂度为O(1)（假设字符串比较耗时常数级）。
   • 空间复杂度：O(n)（归并排序的临时数组）。

6. 边界情况处理

   • 空数组或单元素数组直接返回。
   • 若字符串为Unicode，需确保比较函数支持（如使用语言内置的字典序比较）。