Java 归并排序

归并排序（Merge Sort）是一种基于分治法的排序算法。它将一个大数组分成两个较小的子数组，分别对每个子数组进行排序，然后再将这两个已排序的子数组合并成一个完整的已排序数组。归并排序的时间复杂度为 O(n log n)，其中 n 是数组的大小。

以下是一个 Java 实现归并排序的示例：

public class MergeSort {  // 主函数，用于测试归并排序  public static void main(String[] args) {  int[] array = {38, 27, 43, 3, 9, 82, 10};  System.out.println("给定数组:");  printArray(array);  mergeSort(array, 0, array.length - 1);  System.out.println("\n排序后的数组:");  printArray(array);  }  // 归并排序函数  public static void mergeSort(int[] array, int left, int right) {  if (left < right) {  // 找到中间点  int middle = (left + right) / 2;  // 对左半部分进行排序  mergeSort(array, left, middle);  // 对右半部分进行排序  mergeSort(array, middle + 1, right);  // 合并已排序的左右两部分  merge(array, left, middle, right);  }  }  // 合并函数  public static void merge(int[] array, int left, int middle, int right) {  // 找到两个子数组的大小  int n1 = middle - left + 1;  int n2 = right - middle;  // 创建临时数组  int[] leftArray = new int[n1];  int[] rightArray = new int[n2];  // 拷贝数据到临时数组  for (int i = 0; i < n1; ++i)  leftArray[i] = array[left + i];  for (int j = 0; j < n2; ++j)  rightArray[j] = array[middle + 1 + j];  // 合并临时数组到原数组  // 初始索引分别为两个子数组的起始位置  int i = 0, j = 0;  // 初始索引为合并子数组的起始位置  int k = left;  while (i < n1 && j < n2) {  if (leftArray[i] <= rightArray[j]) {  array[k] = leftArray[i];  i++;  } else {  array[k] = rightArray[j];  j++;  }  k++;  }  // 拷贝左子数组剩余的元素（如果有）  while (i < n1) {  array[k] = leftArray[i];  i++;  k++;  }  // 拷贝右子数组剩余的元素（如果有）  while (j < n2) {  array[k] = rightArray[j];  j++;  k++;  }  }  // 打印数组函数  public static void printArray(int[] array) {  int n = array.length;  for (int i = 0; i < n; ++i)  System.out.print(array[i] + " ");  System.out.println();  }  
}

代码解释：

1. mergeSort 方法：
   • 递归地将数组分成左右两部分，直到每部分只有一个元素或为空。
   • 递归调用 mergeSort 方法对左右两部分进行排序。
   • 调用 merge 方法将已排序的左右两部分合并成一个完整的已排序数组。
2. merge 方法：
   • 创建两个临时数组 leftArray 和 rightArray 分别存储左右两部分。
   • 将左右两部分分别拷贝到临时数组中。
   • 使用两个指针 i 和 j 分别遍历临时数组 leftArray 和 rightArray。
   • 使用一个指针 k 遍历原数组，根据临时数组中的元素大小，将较小的元素依次拷贝回原数组。
   • 如果某一临时数组的元素已经拷贝完，则将另一临时数组的剩余元素拷贝回原数组。
3. printArray 方法：
   • 用于打印数组中的元素。

运行结果：

程序运行后，会先打印给定的数组，然后打印排序后的数组。

归并排序是一个稳定的排序算法，适用于大多数需要排序的场景。它的空间复杂度为 O(n)，因为需要额外的临时数组来存储子数组的元素。