Java对象数组归并排序逻辑错误解析与修正-java教程-PHP中文网

Java对象数组归并排序逻辑错误解析与修正

碧海醫心

发布： 2025-09-13 12:40:15

原创

426人浏览过

Java对象数组归并排序逻辑错误解析与修正

本文旨在深入分析Java中对对象数组执行归并排序时常见的逻辑错误，特别是子数组创建时的System.arraycopy误用以及merge方法中循环结构的不当，导致排序结果异常。通过详细的错误剖析，提供了一套修正后的归并排序实现方案，包括辅助数组复制方法和优化的合并逻辑，确保对象数组能够正确、高效地进行排序。

1. 归并排序核心原理回顾

归并排序（merge sort）是一种基于分治思想的高效排序算法。其基本步骤如下：

分解（Divide）：将待排序的数组递归地分解为两个子数组，直到每个子数组只包含一个元素（单个元素被认为是自然有序的）。
解决（Conquer）：递归地对每个子数组进行排序。
合并（Combine）：将两个已排序的子数组合并成一个更大的有序数组。这个合并过程是归并排序的核心，它通过比较两个子数组的元素，逐个将较小的（或较大的，取决于排序方向）元素放入结果数组中。

2. Box类及其比较逻辑

在处理对象数组的排序时，我们通常需要定义对象之间的比较规则。在本例中，我们有一个Box类，它包含宽度、高度和长度属性，并通过计算体积来定义其比较逻辑。

public class Box {
  private double width, height, length;

  Box(double w, double h, double l){
    width=w;
    height=h;
    length=l;
  }

  private double getVolume(){
    return width*height*length;
  }

  // 按照体积进行比较，用于升序排序
  public int compareTo(Box o){
    double myVol = this.getVolume();
    double thatVol = o.getVolume();
    if (myVol > thatVol)
      return 1;      // 当前对象体积更大
    else if (myVol < thatVol)
      return -1;     // 当前对象体积更小
    else
      return 0;      // 体积相等
  }

  public String toString(){
    return "Width: "+width+
           "\theight: "+height+
            "\tlength: "+length+
            "\tVolume: "+getVolume();
  }
}

登录后复制

compareTo方法是Java中Comparable接口的一部分，它定义了对象之间自然排序的规则。在本例中，compareTo方法根据Box对象的体积进行比较，返回正数、负数或零，分别表示当前对象大于、小于或等于另一个对象。

3. 原始实现中的关键逻辑错误分析

原始的归并排序实现存在两个主要的逻辑错误，导致排序结果不正确，甚至出现所有元素都被同一个对象覆盖的情况。

3.1 子数组创建错误：System.arraycopy的误用

在mergeSort方法中，将原始数组theBoxes分解为firstHalf和secondHalf时，secondHalf的创建方式存在问题：

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

// 原始错误代码片段
static void mergeSort(Box[] theBoxes) {
    if(theBoxes.length > 1 ){
        Box [] firstHalf = new Box[theBoxes.length/2];
        System.arraycopy(theBoxes, 0 , firstHalf, 0 ,theBoxes.length /2); 
        mergeSort(firstHalf);

        int secondHalfLength = theBoxes.length - theBoxes.length / 2 ; 
        Box [] secondHalf = new Box [secondHalfLength];
        // 错误点：secondHalf也从theBoxes的索引0开始复制
        System.arraycopy(theBoxes, 0 , secondHalf, 0 ,secondHalfLength); 
        mergeSort(secondHalf);

        merge(firstHalf, secondHalf , theBoxes); 
    }
}

登录后复制

问题在于secondHalf的创建。System.arraycopy(theBoxes, 0, secondHalf, 0, secondHalfLength); 这行代码将theBoxes数组从索引0开始复制secondHalfLength个元素到secondHalf。这意味着，如果theBoxes是[A, B, C, D]，firstHalf会正确地得到[A, B]，但secondHalf也会得到[A, B]（如果secondHalfLength是2），而不是期望的[C, D]。

这样会导致merge方法在合并时，实际上是在合并两个部分或完全重叠的子数组，而不是两个独立的、已排序的子数组，从而使最终的排序结果错误，甚至可能出现所有元素都变成同一个对象的情况（如果重复合并导致某个特定对象被反复选中）。

3.2 merge方法中的循环结构问题

原始的merge方法在处理合并逻辑时，其内部的循环结构也存在一个不易察觉的错误：

// 原始错误代码片段
static void merge(Box [] list1, Box [] list2 , Box [] temp ){
    int current1 = 0;
    int current2 = 0;
    int current3 = 0; 

    while (current1 < list1.length && current2 < list2.length){
        // 比较逻辑（此处假设为降序，与compareTo的升序定义不符，后面会修正）
        if(list1[current1].compareTo(list2[current2]) > 0){ 
            temp[current3++] = list1[current1++];
        }else{
            temp[current3++] = list2[current2++];
        }

        // 错误点：这两个while循环不应该嵌套在主while循环内部
        while(current1 < list1.length){
            temp[current3++] = list1[current1++];
        }
        while(current2 < list2.length){
            temp[current3++] = list2[current2++];
        }
    }
}

登录后复制

在merge方法中，用于复制剩余元素的两个while循环被错误地放置在了主while (current1 < list1.length && current2 < list2.length)循环的内部。这意味着，只有当主循环的某一次迭代结束后，如果其中一个子列表恰好耗尽，这两个内部循环才会尝试执行。但在主循环的后续迭代中，它们会被跳过。

正确的做法是，主循环负责在两个子数组都有元素时进行比较和合并，而当其中一个子数组耗尽后，将另一个子数组中剩余的所有元素直接复制到目标数组中。因此，这两个处理剩余元素的while循环应该放在主while循环的外部。

挖错网

一款支持文本、图片、视频纠错和AIGC检测的内容审核校对平台。

查看详情

3.3 排序方向与compareTo的匹配

原始merge方法中的比较条件if(list1[current1].compareTo(list2[current2]) > 0)。如果compareTo返回1表示list1的元素更大，那么这个条件成立时，会将list1[current1]放入temp数组。这意味着它在选择更大的元素，从而实现的是降序排序。然而，Box类的compareTo方法通常按照标准约定用于实现升序排序（即this小于o时返回负数）。为了保持一致性并实现升序排序，merge方法中的比较逻辑也需要调整。

4. 修正后的归并排序实现

为了解决上述问题，我们需要对mergeSort和merge方法进行修正。

4.1 arrayCopy辅助方法

为了避免System.arraycopy的误用，我们可以编写一个简单的辅助方法来从源数组的指定范围复制元素到新数组。

static Box[] arrayCopy(Box[] sourceArray, int startIndex, int endIndex) {
    Box[] tempArray = new Box[endIndex - startIndex];
    for (int i = startIndex, m = 0; i < endIndex; i++, m++) {
        tempArray[m] = sourceArray[i];
    }
    return tempArray;
}

登录后复制

这个arrayCopy方法接收源数组、起始索引和结束索引（不包含），然后创建一个新数组，并将指定范围内的元素复制过去。

4.2 修正后的mergeSort方法

使用arrayCopy辅助方法来正确地创建firstHalf和secondHalf子数组。

static void mergeSort(Box[] theBoxes) {
    if (theBoxes.length > 1) {
        int mid = theBoxes.length / 2;

        // 正确创建firstHalf，从theBoxes的0到mid-1
        Box[] firstHalf = arrayCopy(theBoxes, 0, mid);
        mergeSort(firstHalf);

        // 正确创建secondHalf，从theBoxes的mid到theBoxes.length-1
        Box[] secondHalf = arrayCopy(theBoxes, mid, theBoxes.length);
        mergeSort(secondHalf);

        merge(firstHalf, secondHalf, theBoxes);
    }
}

登录后复制

通过arrayCopy(theBoxes, mid, theBoxes.length)，secondHalf现在将正确地包含原始数组的后半部分元素，解决了子数组内容重叠的问题。

4.3 修正后的merge方法

修正merge方法中的循环结构，并将比较逻辑调整为实现升序排序。

static void merge(Box[] list1, Box[] list2, Box[] temp) {
    int current1 = 0; // 指向list1的当前元素
    int current2 = 0; // 指向list2的当前元素
    int current3 = 0; // 指向temp数组的当前位置

    // 当两个子数组都有元素时，进行比较并合并
    while (current1 < list1.length && current2 < list2.length) {
        // 对于升序排序，选择较小的元素放入temp数组
        if (list1[current1].compareTo(list2[current2]) <= 0) { // 如果list1的元素更小或相等
            temp[current3++] = list1[current1++];
        } else { // 如果list2的元素更小
            temp[current3++] = list2[current2++];
        }
    }

    // 将list1中剩余的元素复制到temp数组（如果list2先耗尽）
    while (current1 < list1.length) {
        temp[current3++] = list1[current1++];
    }

    // 将list2中剩余的元素复制到temp数组（如果list1先耗尽）
    while (current2 < list2.length) {
        temp[current3++] = list2[current2++];
    }
}

登录后复制

修正后的merge方法将处理剩余元素的while循环移到了主循环之外，确保了所有元素都能被正确复制。同时，if (list1[current1].compareTo(list2[current2]) <= 0)的比较条件确保了在相等时优先取list1的元素（保持稳定性，虽然对于对象数组通常不强制要求），并实现标准的升序排序。

5. 完整示例代码

结合Box类、修正后的arrayCopy、mergeSort和merge方法，以下是一个完整的Java归并排序示例：

import java.util.Arrays;

public class MergeSortObjects {

    // Box类（保持不变）
    public static class Box {
        private double width, height, length;

        Box(double w, double h, double l) {
            width = w;
            height = h;
            length = l;
        }

        private double getVolume() {
            return width * height * length;
        }

        // 按照体积进行升序比较
        public int compareTo(Box o) {
            double myVol = this.getVolume();
            double thatVol = o.getVolume();
            if (myVol > thatVol)
                return 1;
            else if (myVol < thatVol)
                return -1;
            else
                return 0;
        }

        @Override
        public String toString() {
            return "Width: " + String.format("%.1f", width) +
                   "\theight: " + String.format("%.1f", height

登录后复制

以上就是Java对象数组归并排序逻辑错误解析与修正的详细内容，更多请关注php中文网其它相关文章！