Java实现归并排序

归并排序（Merge Sort）是一种基于分治策略的高效排序算法。它的基本思想是将待排序的元素序列分成两个或更多的子序列，分别对每个子序列进行排序，然后将排好序的子序列合并成一个有序序列。这个过程可以递归进行，直到所有元素都在一个子序列中，形成最终的有序序列。 在Java中实现归并排序，主要涉及到以下几个关键步骤： 1. **分割（Divide）**：将原始数组分为两个相等（或接近相等）的子数组。这通常通过取数组中间索引来完成。例如，如果数组长度为`n`，则可以将前`n/2`个元素作为左子数组，其余元素作为右子数组。 2. **排序（Conquer）**：递归地对左右子数组进行归并排序。如果子数组长度为1，则认为它们已经是有序的，无需再进行操作。 3. **合并（Combine）**：将已排序的子数组合并为一个有序的数组。这是归并排序的核心步骤，通常通过两个指针来实现。遍历两个子数组，每次选取当前较小的元素放入新的结果数组，直到一个子数组为空，然后将另一个子数组的所有剩余元素添加到结果数组中。 以下是一个简单的Java代码实现： ```java public class MergeSort { // 归并排序函数 public static void mergeSort(int[] array, int left, int right) { if (left < right) { int mid = (left + right) / 2; // 对左半部分进行归并排序 mergeSort(array, left, mid); // 对右半部分进行归并排序 mergeSort(array, mid + 1, right); // 合并两个已排序的部分 merge(array, left, mid, right); } } // 合并函数 private static void merge(int[] array, int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; // 创建临时数组 int[] L = new int[n1]; int[] R = new int[n2]; // 将左半部分复制到临时数组L[] System.arraycopy(array, left, L, 0, n1); // 将右半部分复制到临时数组R[] System.arraycopy(array, mid + 1, R, 0, n2); // i指向左半部分的起始位置，j指向右半部分的起始位置，k指向原数组的当前合并位置 int i = 0, j = 0, k = left; // 合并两个子数组 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 static void main(String[] args) { int[] array = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6}; mergeSort(array, 0, array.length - 1); System.out.println("Sorted array: "); for (int value : array) { System.out.print(value + " "); } } } ``` 在这个例子中，`mergeSort()`函数负责调用自身进行递归排序，而`merge()`函数实现了合并两个已排序子数组的过程。在`main()`方法中，我们创建了一个未排序的数组，并调用`mergeSort()`对其进行排序，最后打印出排序后的结果。 归并排序的时间复杂度为O(n log n)，空间复杂度为O(n)，其中n是数组的长度。由于归并排序需要额外的空间来存储子数组，所以它不是原地排序算法。然而，其稳定的排序性质（即相等元素的相对顺序在排序后保持不变）使其在处理大量数据时非常有用，特别是在需要保证排序稳定性的情况下。