本文介绍如何改进快速排序算法，使其在按对象字段（如部门）排序时，自动对重复值按另一字段（如id）进行二级升序排序，避免不稳定排序问题。
本文介绍如何改进快速排序算法，使其在按对象字段（如部门）排序时，自动对重复值按另一字段（如id）进行二级升序排序，避免不稳定排序问题。
在对 Staff 对象数组按 dep（部门）字段进行快速排序时，若多个员工属于同一部门（如多个 "IT"），原始实现仅依赖 dep.compareTo(pivot.dep)，会导致相同部门的元素相对顺序不确定，且无法进一步按 id 排序。要实现稳定、可预测的多级排序（主键：dep 字典序升序；次键：id 数值升序），关键在于将比较逻辑封装到 Staff 类中，并在快排分区过程中统一调用。
✅ 正确做法：在 Staff 类中定义 compareTo 方法
首先，确保 Staff 类实现了合理的比较逻辑（无需实现 Comparable 接口也可，但推荐实现以增强可扩展性）：
public class Staff implements Comparable<Staff> {
int id;
String name;
String dep;
public Staff(int id, String name, String dep) {
this.id = id;
this.name = name;
this.dep = dep;
}
@Override
public int compareTo(Staff other) {
int depCmp = this.dep.compareTo(other.dep);
if (depCmp != 0) return depCmp; // 部门不同，以部门为准
return Integer.compare(this.id, other.id); // 部门相同时，按id升序
}
}? 注意：使用 Integer.compare() 替代 id - other.id 可避免整数溢出风险（如 Integer.MAX_VALUE - Integer.MIN_VALUE）。
? 修改快排逻辑：统一使用 compareTo
将原 quickSort 中所有基于 dep 的字符串比较，替换为对 Staff 对象的 compareTo 调用。同时，pivot 应选取对象引用而非字符串，确保比较语义一致：
private static void quickSort(Staff[] staffs, int start, int end) {
if (start < end) { // 更清晰的边界判断（等价于 j-i >= 1）
int i = start;
int j = end;
Staff pivot = staffs[start]; // 选取首元素为pivot（亦可随机优化）
while (i < j) {
// 从左向右找第一个 > pivot 的元素
while (i < j && staffs[i].compareTo(pivot) <= 0) {
i++;
}
// 从右向左找第一个 < pivot 的元素
while (i < j && staffs[j].compareTo(pivot) >= 0) {
j--;
}
if (i < j) {
swap(staffs, i, j);
}
}
// 将pivot放到最终位置（j是pivot应处的索引）
swap(staffs, start, j);
quickSort(staffs, start, j - 1);
quickSort(staffs, j + 1, end);
}
}⚠️ 注意事项：
- 原代码中 i start 等冗余条件已移除，由外层 while (i
- 分区后 swap(staffs, start, j) 是标准 Lomuto 分区法核心，确保 pivot 归位；
- 若需更高性能与抗退化能力，可引入三数取中或随机化 pivot 选择。
✅ 效果验证
运行修改后的代码，输入数据中 "IT" 部门包含 ID 为 1, 3, 4, 10 的员工，排序后将严格呈现为：
1, J, IT → 3, I, IT → 4, D, IT → 10, C, IT
其他部门同理，整体满足：先按 dep 字典升序，同部门内按 id 数值升序。
? 总结
- 多级排序的本质是定义复合比较规则，应封装在领域对象中（如 compareTo），而非分散在算法逻辑里；
- 快速排序本身不保证稳定性，但通过严谨的 compareTo 实现，可确保相同主键元素按次键有序，达到业务所需的“逻辑稳定”效果；
- 后续如需按 name 或组合更多字段排序，只需扩展 compareTo 方法，快排核心无需改动——体现良好设计的可维护性。
