java实现归并排序

归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列

归并排序原理

如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样子整个数组就有序了。

归并排序使用的是分治思想，分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决，小的子问题解决了，大问题也就解决了。
经过我上述的描述，有没有发现分治思想跟递归思想很像，没错，分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧，两者并不冲突。

代码实现

/**
 * @author Pippen
 * @date 2020-06-30 22:50
 */
public class MyMargeSort {

  public static void myMargeSort(int[] arr,int[] tmp, int start, int mid, int end) {
    int p1 = start, p2 = mid + 1, k = start;
    while (p1 <= mid && p2 <= end) {
      if (arr[p1] <= arr[p2]) {
        tmp[k] = arr[p1];
        p1++;
      } else {
        tmp[k] = arr[p2];
        p2++;
      }
      k++;
    }
    while (p1 <= mid) { // 将未检测的数据进行合并
      tmp[k] = arr[p1];
      k++;
      p1++;
    }
    while (p2 <= end) { // 同上
      tmp[k] = arr[p2];
      k++;
      p2++;
    }
    for (int i = start; i <= end; i++) { // 复制回原数组中
      arr[i] = tmp[i];
    }
  }

  public static void marge(int[] arr, int start, int end) {
    if (start >= end) return; // 递归结束条件
    int[] tmp = new int[arr.length]; // 辅助数组
    int mid = (start + end) / 2; // 划分子序列
    marge(arr, start, mid);
    marge(arr, mid + 1, end);
    myMargeSort(arr,tmp, start, mid, end); // 合并
  }

  public static void main(String[] args) {
    int[] a = {8, 5, 9, 1, 3, 2, 4};
    marge(a, 0, a.length - 1);
    System.out.print("排好序的数组："+ Arrays.toString(a));
  }
}

打赏