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

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

本文讲解如何在 Ja va 中对含重复字段的对象数组（如 Staff）进行快速排序，当主字段（如部门）相同时，按次字段（如员工 ID）升序排序，通过重写 compareTo 方法实现稳定、可扩展的多级比较逻辑。

处理对象数组排序时，一个常见的痛点是什么？是当主排序字段出现大量重复值时，排序的“粒度”就显得不够用了。比如，对一个员工数组按部门排序后，同一个部门里的员工顺序是杂乱无章的，这在实际业务中往往难以接受。更棘手的是，在快速排序这类算法中，重复值还可能导致分区不均，拖累性能。

那么，理想的解决方案是什么？答案是引入多级比较逻辑。具体来说，先按首要字段（如部门）升序排列；当部门相同时，再启用第二级规则，比如按员工ID升序排列。这样，最终结果既清晰又实用。

如何优雅地实现它？最简洁、也最符合面向对象思想的做法，是在业务类内部定义好自然的比较规则。也就是说，让 Staff 类实现 Comparable 接口，并重写其 compareTo 方法。这么做的好处显而易见：将排序规则封装在数据对象内部，实现了算法与业务逻辑的解耦。日后无论是调用 Arrays.sort() 还是放入有序集合，这套比较逻辑都能直接复用。

下面是一个改造后的 Staff 类示例：

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 depCompare = this.dep.compareTo(other.dep);
        if (depCompare != 0) {
            return depCompare; // 部门不同，按部门排序
        }
        return Integer.compare(this.id, other.id); // 部门相同，按ID升序
    }
}

✅ 这里有个细节值得注意：比较整型ID时，推荐使用 Integer.compare(this.id, other.id)，而不是直接做减法 this.id - other.id。为什么？因为后者在极端值（例如 Integer.MAX_VALUE 减去一个负数）时会发生整数溢出，导致比较结果错误。使用标准库方法则安全无忧。

定义好比较规则后，快速排序算法的改造就水到渠成了。核心思路是将原先基于字符串的直接比较，替换为对 compareTo 方法的调用，同时确保基准元素（pivot）的类型是 Staff 对象本身。来看优化后的排序方法：

private static void quickSort(Staff[] staffs, int start, int end) {
    if (start >= end) return;

    int i = start, j = end;
    Staff pivot = staffs[start]; // 以首元素为基准（更稳定，避免边界问题）

    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);
}

⚠️ 关键优化点说明：

• 逻辑解耦：原方案用 pivot = staffs[i].dep，将比较逻辑与对象绑定过紧，难以扩展。新方案直接使用 Staff pivot 并调用其 compareTo 方法，语义清晰，维护性大大增强。
• 条件精简：循环内的条件已经过优化，移除了冗余的 i < end 和 j > start 检查。因为外层的 if (start >= end) 和 while (i < j) 已经充分保证了索引的安全性。
• 基准选择：直接使用 staffs[start] 作为基准，比用 staffs[i]（此时 i 等于 start）更直观，也避免了循环前索引被意外修改的风险。

至于交换元素用的 swap 方法和打印数组的 PrintArray 方法，则保持原样即可。运行之后，输出结果将严格满足两个层次的有序性：
第一，部门名称按字母顺序升序排列（例如 AUDIT → GA → HR → IT）；
第二，同一部门内部，员工ID严格按升序排列（例如IT部门里，原本乱序的 id=1,4,3,10，排序后会变成 1,3,4,10）。

可以说，这种设计不仅漂亮地解决了重复字段下的二级排序难题，其扩展性也相当出色。未来如果需要增加按姓名、入职时间等更多维度排序，只需在 compareTo 方法中继续追加比较逻辑即可，整个排序算法的核心代码完全无需改动。这正体现了良好封装带来的强大灵活性。