如何在对象数组的快速排序中处理重复字段并实现多级排序

如何在对象数组的快速排序中处理重复字段并实现多级排序

当我们对一个员工（Staff）对象数组按照部门（dep）字段进行快速排序时，会遇到一个典型的“业务陷阱”：如果多个员工同属一个部门（比如有好几个“IT”部门的同事），原始的排序逻辑仅仅比较dep字符串，那么这些同部门员工的最终顺序就成了“听天由命”，既不稳定，也无法按照我们可能期望的工号（id）进行次级排序。这显然不符合实际业务中对数据清晰、可预测的要求。今天要探讨的，就是如何改造快速排序算法，让它不仅能按主字段排序，还能在遇到重复值时，自动、智能地按我们预设的次字段进行排序，从而输出一个既稳定又符合复杂业务逻辑的结果。

✅ 正确做法：在 Staff 类中定义 compareTo 方法

解决问题的核心思路，其实在于“封装”。与其在排序算法里写一堆复杂的、针对具体字段的判断，不如把“如何比较两个员工对象”这个规则，定义在员工类本身。这就像给每个员工发一本统一的“比较手册”，排序算法只需要翻手册办事就行。

具体来说，就是让Staff类实现Comparable接口，并在compareTo方法中明确多级排序的规则：先按部门名字典序排，部门相同再按工号升序排。

public class Staff implements Comparable {
    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(this.id, other.id)，而不是直接做减法this.id - other.id。为什么？这是为了规避潜在的整数溢出风险。想象一下，一个接近最大值的正数减去一个接近最小值的负数，结果可能会超出整型范围，导致比较出错。使用标准库方法则安全无忧。

? 修改快排逻辑：统一使用 compareTo

定义好了比较规则，接下来就要让快速排序算法“学会”使用它。改造的关键有两点：一是将所有原来直接比较dep字符串的地方，替换为调用staff.compareTo(pivot)；二是确保基准元素（pivot）本身也是一个Staff对象引用，而不是一个孤立的字符串，这样才能保证比较语义的一致性。

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 < end和j > start已被移除，边界控制完全交由外层while (i < j)和内层循环的条件负责，逻辑更清晰。
• swap(staffs, start, j)这一步是经典Lomuto分区法的核心操作，它确保了基准元素pivot在分区结束后被放置到其最终的正确位置上。
• 如果追求极致的性能与应对极端数据（如已排序数组）的能力，可以考虑引入“三数取中”法或随机化选择pivot的策略来优化。

✅ 效果验证

经过以上改造，算法现在具备了“多级排序”的智慧。拿一组数据来测试：假设“IT”部门有工号为1、3、4、10的四位员工。运行修改后的排序算法，你会看到他们的顺序被严格排列为：工号1 → 工号3 → 工号4 → 工号10。其他部门也遵循同样的规则。最终，整个数组会呈现出我们期望的完美状态：首先，所有员工按部门名称的字典顺序升序排列；其次，在同一部门内部，员工严格按照工号数值升序排列。

? 总结

• 封装比较逻辑：多级排序的本质是定义一套清晰的复合比较规则。最佳实践是将此规则封装在业务对象内部（如实现compareTo方法），而不是散落在排序算法中。这体现了“高内聚、低耦合”的设计思想。
• 理解“稳定性”：标准的快速排序算法本身是不稳定的，但这并不妨碍我们实现业务层面的“逻辑稳定”。通过严谨的compareTo实现，我们确保了拥有相同主键（部门）的元素，必然会按照我们指定的次键（工号）顺序出现，从而满足了业务对确定性的要求。
• 拥抱可扩展性：这种设计的优势在于其强大的可维护性。未来，如果排序需求发生变化，比如需要加入按姓名（name）排序作为第三级规则，或者调整排序的优先级，我们只需要修改Staff类中的compareTo方法即可，快速排序的核心算法部分完全无需改动。这为代码的长期演进提供了极大的便利。