Java实现归并排序算法的代码 |21xrx.com

Java实现归并排序算法的代码

2023-07-26 20:02:28 深夜i 18 0

Java 归并排序算法代码实现

归并排序是一种经典的排序算法，其思想是将待排序的序列分成两个子序列，分别对这两个子序列进行排序，然后将两个已经有序的子序列合并成一个有序的序列。该算法的时间复杂度为O(nlogn)，其实现可以使用Java语言来实现。

下面是Java实现归并排序算法的代码：

public class MergeSort {
  public void mergeSort(int[] array) {
    if (array == null || array.length <= 1)
      return;
    
    int[] temp = new int[array.length];
    mergeSort(array, temp, 0, array.length - 1);
  }
  private void mergeSort(int[] array, int[] temp, int left, int right) {
    if (left >= right)
      return;
    
    int mid = (left + right) / 2;
    mergeSort(array, temp, left, mid);
    mergeSort(array, temp, mid + 1, right);
    merge(array, temp, left, mid, right);
  }
  private void merge(int[] array, int[] temp, int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= right) {
      if (array[i] <= array[j]) {
        temp[k++] = array[i++];
      } else {
        temp[k++] = array[j++];
      }
    }
    while (i <= mid) {
      temp[k++] = array[i++];
    }
    while (j <= right) {
      temp[k++] = array[j++];
    }
    for (int m = 0; m < k; m++) {
      array[left + m] = temp[m];
    }
  }
  public static void main(String[] args) {
    int[] array = 1;
    MergeSort mergeSort = new MergeSort();
    mergeSort.mergeSort(array);
    for (int num : array) {
      System.out.print(num + " ");
    }
  }
}

以上是一个简单的Java实现归并排序算法的示例代码。在这段代码中，我们使用了递归的方式来进行归并排序。首先，我们将待排序的序列分为两个子序列，分别对这两个子序列进行递归排序。然后，我们再将这两个已经有序的子序列进行合并，形成一个有序的序列。

在递归的函数`mergeSort`中，我们首先进行递归终止条件的判断，即当序列为空或者长度为1时，直接返回。接着，我们创建一个临时数组用于存储合并后的结果。然后，我们调用`mergeSort`函数对左右两个子序列进行递归排序，并最后调用`merge`函数将这两个已经有序的子序列合并。

`merge`函数中，我们使用三个指针i、j和k分别指向左子序列、右子序列和临时数组的位置，通过比较左右子序列的元素大小，将较小元素存入临时数组中。最后，我们将临时数组中的元素复制回原序列中。

在`main`函数中，我们定义了一个待排序的数组，并创建一个`MergeSort`对象，调用`mergeSort`函数对数组进行归并排序。然后，我们打印排序后的结果。

归并排序是一种稳定的排序算法，其时间复杂度为O(nlogn)，适用于各种数据规模的排序问题。通过使用Java语言实现归并排序算法，我们可以更好地理解该算法的思想和过程。

上一篇: idea打包java可执行jar包

下一篇: 如何在ffmpeg中探索黑科技技巧

评论区

相似文章