跳到主要内容

Java程序实现归并排序算法

要理解这个示例，你应该具备以下 Java 编程 主题的知识：

Java 中的归并排序​

归并排序算法基于分而治之的原则，即将一个问题分解成多个子问题。每个子问题分别解决后，再将子问题的解决方案组合成最终的解决方案。

要了解更多，请访问 归并排序算法。

示例：Java 程序实现归并排序算法​

import java.util.Arrays;

// Java 中的归并排序

class Main {

  // 将两个子数组 L 和 M 合并为一个数组
  void merge(int array[], int p, int q, int r) {

    int n1 = q - p + 1;
    int n2 = r - q;

    int L[] = new int[n1];
    int M[] = new int[n2];

    // 填充左右数组
    for (int i = 0; i < n1; i++)
      L[i] = array[p + i];
    for (int j = 0; j < n2; j++)
      M[j] = array[q + 1 + j];

    // 维护子数组和主数组的当前索引
    int i, j, k;
    i = 0;
    j = 0;
    k = p;

    // 直到 L 或 M 的任一端结束，从 L 和 M 中选取较大的元素，并放在 A[p..r] 的正确位置
    // 用于降序排序
    // 使用 if(L[i] >= M[j])
    while (i < n1 && j < n2) {
      if (L[i] <= M[j]) {
        array[k] = L[i];
        i++;
      } else {
        array[k] = M[j];
        j++;
      }
      k++;
    }

    // 当 L 或 M 的元素用完时，
    // 取剩余元素放入 A[p..r]
    while (i < n1) {
      array[k] = L[i];
      i++;
      k++;
    }

    while (j < n2) {
      array[k] = M[j];
      j++;
      k++;
    }
  }

  // 将数组分成两个子数组，排序并合并它们
  void mergeSort(int array[], int left, int right) {
    if (left < right) {

      // m 是将数组分成两个子数组的点
      int mid = (left + right) / 2;

      // 递归调用每个子数组
      mergeSort(array, left, mid);
      mergeSort(array, mid + 1, right);

      // 合并已排序的子数组
      merge(array, left, mid, right);
    }
  }

  public static void main(String args[]) {

    // 创建一个未排序的数组
    int[] array = { 6, 5, 12, 10, 9, 1 };

    Main ob = new Main();

    // 调用方法 mergeSort()
    // 传递参数：数组，起始索引和末尾索引
    ob.mergeSort(array, 0, array.length - 1);

    System.out.println("排序后的数组:");
    System.out.println(Arrays.toString(array));
  }
}

输出 1

未排序的数组:
[6, 5, 12, 10, 9, 1]
排序后的数组:
[1, 5, 6, 9, 10, 12]

这里，数组的元素按升序排列。如果我们想按降序排序元素，那么在 merge() 方法的第一个 while 循环中，我们可以更改代码为：

// 小于号更改为大于号
if (L[i] >= M[j]) {
最后于 更新