归并排序：JAVA

主函数 main

public static void main(String[] args) {
    int[] arr = {12, 11, 13, 5, 6, 7};
    System.out.println("Given Array");
    printArray(arr);

    MergeSort ob = new MergeSort();
    ob.sort(arr, 0, arr.length - 1);

    System.out.println("\nSorted array");
    printArray(arr);
}

这个程序展示了如何使用Java实现归并排序，并且通过示例数组进行了测试。你可以根据需要修改输入数组或添加更多的功能。

• 功能: 程序的入口点，用于初始化一个数组并调用归并排序算法对其进行排序。
• 步骤:
• 定义一个整数数组 arr。
• 打印原始数组。
• 创建 MergeSort 类的实例 ob。
• 调用 ob 的 sort 方法对数组进行排序。
• 归并排序函数

•  sort打印排序后的数组。

• ---

  void sort(int arr[], int l, int r) {
      if (l < r) {
          // 找到中间点
          int m = (l + r) / 2;
  
          // 对左半部分进行排序
          sort(arr, l, m);
          // 对右半部分进行排序
          sort(arr, m + 1, r);
  
          // 合并两个已排序的部分
          merge(arr, l, m, r);
      }
  }
  

• 功能: 递归地将数组分成两半，分别对每一半进行排序，然后合并这两部分。
• 参数:
  • arr: 要排序的数组。
  • l: 当前子数组的起始索引。
  • r: 当前子数组的结束索引。
• 步骤:
• 如果 l 小于 r，则继续分割数组。
• 计算中间点 m。
• 递归地对左半部分（从 l 到 m）进行排序。
• 递归地对右半部分（从 m+1 到 r）进行排序。
• 调用 merge 方法合并两个已排序的部分。

• 合并函数 merge

• void merge(int arr[], int l, int m, int r) {
      // 找出左右子数组的大小
      int n1 = m - l + 1;
      int n2 = r - m;
  
      // 创建临时数组
      int L[] = new int[n1];
      int R[] = new int[n2];
  
      // 复制数据到临时数组中
      for (int i = 0; i < n1; ++i)
          L[i] = arr[l + i];
      for (int j = 0; j < n2; ++j)
          R[j] = arr[m + 1 + j];
  
      // 合并临时数组
      int i = 0, j = 0;
      int k = l;
      while (i < n1 && j < n2) {
          if (L[i] <= R[j]) {
              arr[k] = L[i];
              i++;
          } else {
              arr[k] = R[j];
              j++;
          }
          k++;
      }
  
      // 复制剩余的元素（如果有的话）
      while (i < n1) {
          arr[k] = L[i];
          i++;
          k++;
      }
      while (j < n2) {
          arr[k] = R[j];
          j++;
          k++;
      }
  }
  

• 功能: 合并两个已排序的子数组。
• 参数:
  • arr: 要合并的数组。
  • l: 左子数组的起始索引。
  • m: 中间索引，分隔左右子数组。
  • r: 右子数组的结束索引。
• 步骤:
• 计算左右子数组的大小 n1 和 n2。
• 创建两个临时数组 L 和 R，分别存储左右子数组的数据。
• 将原数组中的数据复制到临时数组 L 和 R。
• 使用双指针法合并两个临时数组，将较小的元素放入原数组中。
• 如果其中一个临时数组还有剩余元素，将其全部复制到原数组中。

• 打印数组函数 printArray

• static void printArray(int arr[]) {
      int n = arr.length;
      for (int i = 0; i < n; ++i)
          System.out.print(arr[i] + " ");
      System.out.println();
  }
  

• 功能: 打印数组的内容。
• 参数: arr，要打印的数组。
• 步骤:
• 获取数组的长度 n。
• 遍历数组，逐个打印每个元素，并在元素之间添加空格。
• 打印完所有元素后换行。

• public class MergeSort {
      // 主函数，用于调用归并排序
      public static void main(String[] args) {
          int[] arr = {12, 11, 13, 5, 6, 7};
          System.out.println("Given Array");
          printArray(arr);
  
          MergeSort ob = new MergeSort();
          ob.sort(arr, 0, arr.length - 1);
  
          System.out.println("\nSorted array");
          printArray(arr);
      }
  
      // 归并排序函数
      void sort(int arr[], int l, int r) {
          if (l < r) {
              // 找到中间点
              int m = (l + r) / 2;
  
              // 对左半部分进行排序
              sort(arr, l, m);
              // 对右半部分进行排序
              sort(arr, m + 1, r);
  
              // 合并两个已排序的部分
              merge(arr, l, m, r);
          }
      }
  
      // 合并函数
      void merge(int arr[], int l, int m, int r) {
          // 找出左右子数组的大小
          int n1 = m - l + 1;
          int n2 = r - m;
  
          // 创建临时数组
          int L[] = new int[n1];
          int R[] = new int[n2];
  
          // 复制数据到临时数组中
          for (int i = 0; i < n1; ++i)
              L[i] = arr[l + i];
          for (int j = 0; j < n2; ++j)
              R[j] = arr[m + 1 + j];
  
          // 合并临时数组
          int i = 0, j = 0;
          int k = l;
          while (i < n1 && j < n2) {
              if (L[i] <= R[j]) {
                  arr[k] = L[i];
                  i++;
              } else {
                  arr[k] = R[j];
                  j++;
              }
              k++;
          }
  
          // 复制剩余的元素（如果有的话）
          while (i < n1) {
              arr[k] = L[i];
              i++;
              k++;
          }
          while (j < n2) {
              arr[k] = R[j];
              j++;
              k++;
          }
      }
  
      // 打印数组的函数
      static void printArray(int arr[]) {
          int n = arr.length;
          for (int i = 0; i < n; ++i)
              System.out.print(arr[i] + " ");
          System.out.println();
      }
  }
  

  代码解释：

• main方法：初始化一个数组并调用sort方法对其进行排序，然后打印排序后的数组。
• sort方法：这是归并排序的核心递归方法。它首先检查数组是否至少有两个元素（即l < r），然后找到中间点m，递归地对左半部分和右半部分进行排序，最后调用merge方法将它们合并。
• merge方法：这个方法负责将两个已经排序的子数组合并成一个有序的数组。它使用两个临时数组L和R来存储左右子数组的数据，然后通过比较这两个临时数组中的元素，将较小的元素放入原数组中。
• printArray方法：这是一个辅助方法，用于打印数组的内容。