Java 菜鸟教程

Java 流程控制

Java 数组

Java 面向对象(I)

Java 面向对象(II)

Java 面向对象(III)

Java 异常处理

Java 列表(List)

Java Queue(队列)

Java Map集合

Java Set集合

Java 输入输出(I/O)

Java Reader/Writer

Java 其他主题

Java 程序实现合并排序算法

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] >= <[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]) {

Java 实例大全