java 数组归并排序

### Java 实现数组归并排序 归并排序是一种分治算法，其核心思想是将数组分成若干子数组分别进行排序，然后再逐步合并这些已排序的子数组以形成最终的有序数组。以下是基于提供的引用内容以及标准实现方法的一个完整示例。 #### 完整代码示例 以下是一个完整的 Java 类 `MergeSort` 的定义及其使用方式： ```java public class MergeSort { // 主函数：执行归并排序 public void sort(int[] array, int leftIndex, int rightIndex) { if (leftIndex < rightIndex) { int middle = (leftIndex + rightIndex) / 2; sort(array, leftIndex, middle); // 对左半部分递归排序 sort(array, middle + 1, rightIndex); // 对右半部分递归排序 merge(array, leftIndex, middle, rightIndex); // 合并两部分 } } // 合并两个有序子数组 private void merge(int[] array, int leftIndex, int middle, int rightIndex) { int n1 = middle - leftIndex + 1; // 左半部分长度 int n2 = rightIndex - middle; // 右半部分长度 // 创建临时数组存储左右两部分数据 int[] L = new int[n1]; int[] R = new int[n2]; for (int i = 0; i < n1; ++i) { L[i] = array[leftIndex + i]; } for (int j = 0; j < n2; ++j) { R[j] = array[middle + 1 + j]; } // 合并过程 int i = 0, j = 0; int k = leftIndex; while (i < n1 && j < n2) { if (L[i] <= R[j]) { array[k++] = L[i++]; } else { array[k++] = R[j++]; } } // 处理剩余元素 while (i < n1) { array[k++] = L[i++]; } while (j < n2) { array[k++] = R[j++]; } } } // 测试类 public class TestMergeSort { public static void main(String[] args) { int[] array = {38, 27, 43, 3, 9, 82, 10}; System.out.println("原始数组:"); printArray(array); MergeSort ms = new MergeSort(); ms.sort(array, 0, array.length - 1); System.out.println("\n排序后的数组:"); printArray(array); } // 打印数组工具方法 public static void printArray(int[] array) { for (int num : array) { System.out.print(num + " "); } System.out.println(); } } ``` 上述代码实现了归并排序的核心逻辑，并通过递归的方式分解问题规模[^1][^3]。具体来说，它先将数组分为尽可能小的部分（即单个元素），再逐一比较相邻的小数组并将它们按顺序合并起来。 --- ### 关键点解析 1. **递归拆分** 使用 `(leftIndex + rightIndex) / 2` 计算中间索引位置，从而将原数组划分为左右两部分。每次递归调用都会进一步缩小范围直到无法继续分割为止[^4]。 2. **合并操作** 在 `merge` 方法中完成实际的数据整理工作。该阶段会依次对比来自左侧和右侧分区中的最小值，并将其放入目标数组相应的位置上。 3. **时间复杂度分析** 归并排序的时间复杂度为 O(n log n)，其中 n 表示输入列表大小。这是因为每一层都需要遍历整个序列一次来完成合并动作；而总共有约 log₂n 层次结构需要处理。 ---