Java归并排序：修复数组元素覆盖问题及代码优化

本文旨在解决Java实现归并排序时出现的数组元素覆盖问题，该问题导致排序只能处理少量元素。文章将分析问题代码，指出错误原因，并提供修正后的代码示例。此外，还会探讨代码风格优化，建议使用接口而非具体类进行编程。

问题分析

提供的Java代码实现了归并排序算法，但存在一个关键错误，导致在合并过程中覆盖了原始数组 a 中的元素。具体来说，错误发生在 merge 方法的最后一步，它使用 a.add(from+j, b.get(j)) 将排序后的元素添加到数组 a 中。add 方法会在指定位置插入元素，导致数组长度增加，并移动后续元素，从而覆盖了未排序的部分。

解决方案

正确的做法是使用 a.set(from+j, b.get(j)) 替换 a.add(from+j, b.get(j))。set 方法用于替换指定位置的元素，而不会改变数组的长度。

修改后的 merge 方法如下：

立即学习“Java免费学习笔记（深入）”；

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

通过将 add 替换为 set，可以确保合并后的元素正确地替换原始数组中的相应位置，从而实现完整的归并排序。

Cursor

一个新的IDE，使用AI来帮助您重构、理解、调试和编写代码。

下载

代码风格优化

在Java编程中，推荐使用接口而非具体类进行编程，这有助于提高代码的灵活性和可维护性。例如，可以将 ArrayList 替换为 List。

修改后的代码示例：

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

public class MergeSort {

    public static void mergeSort(List 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(List a, Integer from, Integer mid, Integer to) {
        Integer n = to - from + 1;
        List 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));
        }
    }

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

        mergeSort(patients, 0, patients.size() - 1);

        System.out.println("Sorted patients: " + patients);
    }
}

在这个修改后的版本中，mergeSort 和 merge 方法的参数类型都从 ArrayList 更改为 List。 这样，你可以更容易地将 mergeSort 方法与不同的 List 实现一起使用，例如 LinkedList，而无需修改 mergeSort 方法本身。

总结

本文详细分析了Java归并排序中出现的数组元素覆盖问题，并提供了解决方案，即将 add 方法替换为 set 方法。此外，还讨论了代码风格优化，建议使用接口而非具体类进行编程。通过这些改进，可以确保归并排序算法的正确性和代码的可维护性。