Java归并排序仅能排序4个元素问题排查及患者病情关联需求

1. 归并排序核心bug修复 #

你的代码在merge方法的最后一步犯了关键错误：用a.add(from+j, b.get(j))是插入新元素而非替换原位置元素，这会导致原数组的元素被向后挤压，数组长度不断膨胀，元素数量越多，覆盖/重复的问题越明显。

修复后的merge方法：

public static void merge(ArrayList<String> a, Integer from, Integer mid, Integer to) {
    Integer n = to - from + 1;
    ArrayList<String> b = new ArrayList<>(n);
    Integer i1 = from;
    Integer i2 = mid + 1;

    // 合并两个子数组到临时数组b
    while (i1 <= mid && i2 <= to) {
        if (a.get(i1).compareTo(a.get(i2)) < 0) {
            b.add(a.get(i1));
            i1++;
        } else {
            b.add(a.get(i2));
            i2++;
        }
    }
    // 处理第一个子数组剩余元素
    while (i1 <= mid) {
        b.add(a.get(i1));
        i1++;
    }
    // 处理第二个子数组剩余元素
    while (i2 <= to) {
        b.add(a.get(i2));
        i2++;
    }
    // 关键修复：用set替换原位置元素，而非add插入
    for (int j = 0; j < n; j++) {
        a.set(from + j, b.get(j));
    }
}

改动说明：把add改成set，让排序后的元素覆盖原数组对应位置的内容，而非插入新元素导致数组结构混乱。

2. 实现患者与病情的关联排序 #

单独排序姓名列表无法保留病情关联，建议创建Patient类封装两个属性，通过实现Comparable接口定义姓名排序规则：

步骤1：定义Patient类 #

public class Patient implements Comparable<Patient> {
    private String name;
    private String condition;

    public Patient(String name, String condition) {
        this.name = name;
        this.condition = condition;
    }

    // Getter方法
    public String getName() { return name; }
    public String getCondition() { return condition; }

    // 按姓名字母序排序
    @Override
    public int compareTo(Patient other) {
        return this.name.compareTo(other.name);
    }

    // 重写toString方便展示
    @Override
    public String toString() {
        return "患者：" + name + "，病情：" + condition;
    }
}

步骤2：修改归并排序适配Patient类 #

只需把泛型从String改为Patient即可，因为Patient已经实现了排序逻辑：

public static void mergeSort(ArrayList<Patient> a, Integer from, Integer to) {
    if (from == to) {
        return;
    }
    Integer mid = (from + to) / 2;
    mergeSort(a, from, mid);
    mergeSort(a, mid + 1, to);
    merge(a, from, mid, to);
}

public static void merge(ArrayList<Patient> a, Integer from, Integer mid, Integer to) {
    Integer n = to - from + 1;
    ArrayList<Patient> b = new ArrayList<>(n);
    Integer i1 = from;
    Integer i2 = mid + 1;

    while (i1 <= mid && i2 <= to) {
        // 直接调用Patient的compareTo方法比较姓名
        if (a.get(i1).compareTo(a.get(i2)) < 0) {
            b.add(a.get(i1));
            i1++;
        } else {
            b.add(a.get(i2));
            i2++;
        }
    }

    while (i1 <= mid) {
        b.add(a.get(i1));
        i1++;
    }

    while (i2 <= to) {
        b.add(a.get(i2));
        i2++;
    }

    // 替换原数组元素
    for (int j = 0; j < n; j++) {
        a.set(from + j, b.get(j));
    }
}

步骤3：使用示例 #

public static void main(String[] args) {
    ArrayList<Patient> patients = new ArrayList<>();
    patients.add(new Patient("Bob", "感冒"));
    patients.add(new Patient("Alice", "高血压"));
    patients.add(new Patient("Charlie", "糖尿病"));
    patients.add(new Patient("David", "哮喘"));
    patients.add(new Patient("Eve", "过敏"));

    // 调用排序，注意to参数是数组最后一个元素的索引
    mergeSort(patients, 0, patients.size() - 1);

    // 打印排序后的关联结果
    for (Patient p : patients) {
        System.out.println(p);
    }
}

3. 额外注意事项 #

• 调用mergeSort时，to参数必须传入list.size() - 1，否则会触发数组越界错误。
• 如果需要灵活切换排序规则（比如按病情排序），可以不用让Patient实现Comparable，而是在merge方法中传入Comparator<Patient>参数自定义排序逻辑。

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