本文深入探讨了Java归并排序中常见的实现陷阱，特别是merge操作中误用ArrayList.add()而非set()导致的数据覆盖问题。通过对比分析，文章详细阐述了正确的元素替换机制，并提供了优化后的代码示例。同时，还介绍了Java编程中面向接口编程的最佳实践，并扩展讨论了如何对自定义对象进行排序，确保数据关联性，旨在帮助开发者构建健壮、高效的排序逻辑。
理解归并排序的核心原理
归并排序是一种基于分治策略的高效稳定排序算法。它将一个大问题分解为若干个小问题，递归地解决这些小问题，然后将小问题的解合并起来，从而解决大问题。其核心步骤包括：
- 分解（Divide）：将待排序数组（或列表）从中间一分为二。
- 解决（Conquer）：递归地对左右两半部分进行排序。
- 合并（Combine）：将两个已排序的子数组（或子列表）合并成一个完整的有序数组（或列表）。
在Java实现中，mergeSort方法负责递归地分解和调用自身，直到子问题足够小（通常是单个元素）。merge方法则承担了将两个有序子列表合并成一个新有序列表的关键任务。
核心问题：ArrayList.add()与ArrayList.set()的误用
在原始的归并排序实现中，merge方法在将临时排序结果复制回原数组a时，使用了a.add(from + j, b.get(j));。这是导致排序功能异常，尤其是在元素数量超过少数几个（如3-4个）时出现数据覆盖或错位问题的根本原因。
-
ArrayList.add(index, element)的行为分析：add(index, element)方法的作用是在指定索引index处“插入”element。当在非末尾位置插入元素时，该位置及之后的所有现有元素都会向后移动一位，并且ArrayList的实际大小会增加。在归并操作中，a数组的长度在每次add调用时都会不断增长，这不仅改变了数组的原始结构，还会导致原有的数据被错误地移动或丢失，从而表现为“覆盖”或混乱的排序结果。
-
ArrayList.set(index, element)的正确性：set(index, element)方法的作用是“替换”指定索引index处的现有元素为element。它不会改变ArrayList的容量，也不会移动其他元素，只是简单地将index位置的旧元素替换为新元素。这正是归并操作中将临时排序结果放回原位置所需要的行为，确保了原数组在指定范围内的元素被正确地更新为排序后的值。
立即学习“Java免费学习笔记（深入）”；
修正后的merge方法
将merge方法中最后的数据回写循环由add改为set即可解决数据覆盖问题。
import java.util.ArrayList; import java.util.List; // 导入List接口 public class MergeSortExample { /** * 归并排序主方法 * @param a 待排序的列表 * @param from 排序范围的起始索引（包含） * @param to 排序范围的结束索引（包含） */ public static void mergeSort(List<String> a, Integer from, Integer to) { // 基本情况：如果from大于或等于to，表示子列表只有一个元素或为空，无需排序 if (from >= to) { return; } // 计算中间索引 Integer mid = (from + to) / 2; // 递归地对左半部分进行排序 mergeSort(a, from, mid); // 递归地对右半部分进行排序 mergeSort(a, mid + 1, to); // 合并两个已排序的子列表 merge(a, from, mid, to); } /** * 合并两个有序子列表的方法 * @param a 原始列表，用于存储合并结果 * @param from 第一个子列表的起始索引 * @param mid 第一个子列表的结束索引 / 第二个子列表的起始索引前一个 * @param to 第二个子列表的结束索引 */ public static void merge(List<String> a, Integer from, Integer mid, Integer to) { // 计算当前合并范围的元素总数 Integer n = to - from + 1; // 创建一个临时列表b，用于存储合并后的有序元素 List<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++; } } // 将第一个子列表剩余的元素添加到临时列表b中（如果有） while (i1 <= mid) { b.add(a.get(i1)); i1++; } // 将第二个子列表剩余的元素添加到临时列表b中（如果有） while (i2 <= to) { b.add(a.get(i2)); i2++; } // 将临时列表b中的排序结果复制回原列表a的相应位置 // 关键修正：使用set而非add，以替换现有元素而不是插入新元素 for (int j = 0; j < n; j++) { a.set(from + j, b.get(j)); } } public static void main(String[] args) { ArrayList<String> patients
评论（已关闭）
评论已关闭