Java归并排序：修复排序不完整的问题_技术教程

本文旨在解决Java中使用归并排序算法时，仅对部分元素进行排序的问题。通过分析错误代码，找出问题根源在于ArrayList的错误使用，并提供正确的代码实现。同时，强调面向接口编程的重要性，提升代码的可维护性和扩展性。

在使用归并排序算法对Java中的ArrayList进行排序时，可能会遇到排序不完整，只对部分元素生效的问题。这通常是由于在合并(merge)步骤中，错误地使用了ArrayList的add()方法，导致数组长度不断增加，最终覆盖了原始数据。下面将详细分析问题原因，并提供正确的解决方案。

问题分析

原始代码的merge()方法中，在将临时数组b中的元素复制回原始数组a时，使用了a.add(from+j, b.get(j))。add(index, element)方法会在指定索引处插入元素，导致该索引及其后面的元素后移，从而改变了ArrayList的长度。在归并排序的递归过程中，多次调用merge()方法，每次都增加ArrayList的长度，最终导致数据被覆盖和排序结果错误。

解决方案

正确的做法是使用a.set(from+j, b.get(j))。set(index, element)方法会将指定索引处的元素替换为新元素，而不会改变ArrayList的长度。这样可以确保合并操作正确地将排序后的元素放回原始数组的正确位置。

以下是修改后的merge()方法：

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

    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++;
        }
        j++;
    }

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

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

    for (j = 0; j < n; j++) {
        a.set(from + j, b.get(j));
    }
}

完整代码示例

以下是完整的归并排序代码示例，包括mergeSort()和修改后的merge()方法：

import java.util.ArrayList;
import java.util.List;

public class MergeSort {

    public static void mergeSort(ArrayList a, Integer from, Integer to) {
        if (from >= to) { // 修改：from == to 改为 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 a, Integer from, Integer mid, Integer to) {
        Integer n = to - from + 1;
        List b = new ArrayList<>(n); // 使用 List 接口
        Integer i1 = from;
        Integer i2 = mid + 1;
        Integer j = 0;

        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++;
            }
            j++;
        }

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

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

        for (j = 0; j < n; j++) {
            a.set(from + j, b.get(j));
        }
    }

    public static void main(String[] args) {
        ArrayList names = new ArrayList<>();
        names.add("Charlie");
        names.add("Alice");
        names.add("Bob");
        names.add("David");
        names.add("Eve");

        System.out.println("排序前: " + names);
        mergeSort(names, 0, names.size() - 1);
        System.out.println("排序后: " + names);
    }
}

注意事项与最佳实践

边界条件检查: 递归的终止条件需要仔细检查，确保不会发生数组越界。例如，from == to 应该改为 from >= to。
面向接口编程: 在声明变量时，推荐使用接口而不是具体的类。例如，使用 List b = new ArrayList(n); 而不是 ArrayList b = new ArrayList(n);。这样做的好处是，如果将来需要更换ArrayList为其他List实现，代码的改动会更小。
代码调试: 在编写复杂算法时，充分利用调试工具，逐步跟踪代码的执行过程，可以帮助快速定位问题。例如，观察ArrayList在merge()方法中的变化，可以很容易地发现add()方法导致的问题。
泛型: 考虑使用泛型，使代码更通用，例如 public static > void mergeSort(List a, int from, int to)。