java 中归并排序算法详解

java 中归并排序算法详解

归并排序算法，顾名思义，是一种先分再合的算法，其算法思想是将要排序的数组分解为单个的元素，每个元素就是一个单个的个体，然后将相邻的两个元素进行从小到大或从大到小的顺序排序组成一个整体，每个整体包含一到两个元素，然后对相邻的整体继续“合”并，因为每个整体都是排过序的，因而可以采用一定的算法对其进行合并，合并之后每个整体包含三到四个元素，继续对相邻的整体进行合并，直到所有的整体都合并为一个整体，最终得到的整体就是将原数组进行排序之后的结果。

对于相邻的整体，其合并的思想是每次都取两个整体（假设其实按升序排序的）中最小的元素放到一个新数组中，依次循环，最终两个整体中的元素都被取完即可得到一个按升序排序的整体。该合并过程就像有两个升序排序的牌堆A和B（如图所示），每次从最顶上取出一个元素放到牌堆C中：

从图中可以看出，对于两个相邻的整体A和B，其内的元素都是按升序排序的，现在有一个临时数组C，然后对A和B顶部的两个元素进行比较，取出较小的一个元素放入C中，对于取出元素的整体，其指向元素的下标下移一位，继续取出两个整体中顶部元素较小的一个放入C中，依次循环，当某个整体元素取完之后直接将另一个整体的元素都移入C中。对于C这个整体，其就是经过A和B排序而得到的，由于A和B是相邻的两个整体，因而，最后只需要将C中的元素复制到A和B组成的一个共同整体中即可，这样也就达到了将A和B合并的同时进行排序的目的。

以下是归并排序的具体算法：

public class MergeSort {
 public static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] arr) {
  AnyType[] tmp = ((AnyType[]) new Comparable[arr.length]);
  mergeSort(arr, 0, arr.length - 1, tmp);
 }

 private static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] arr, int start, int end, AnyType[] tmp) {
  if (start < end) {
   int mid = (start + end) >> 1;
   mergeSort(arr, start, mid, tmp);
   mergeSort(arr, mid + 1, end, tmp);
   merge(arr, start, mid, end, tmp);
  }
 }

 private static <AnyType extends Comparable<? super AnyType>> void merge(AnyType[] arr, int start, int mid, int end, AnyType[] tmp) {
  int i = start, j = mid + 1, k = start;
  while (i <= mid && j <= end) {
   if (arr[i].compareTo(arr[j]) < 0) {
    tmp[k++] = arr[i++];
   } else {
    tmp[k++] = arr[j++];
   }
  }

  while (i <= mid) {
   tmp[k++] = arr[i++];
  }

  while (j <= end) {
   tmp[k++] = arr[j++];
  }

  for (int m = start; m <= end; m++) {
   arr[m] = tmp[m];
  }
 }
}

代码中主要有两个方法

private static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] arr, int start, int end, AnyType[] tmp)

private static <AnyType extends Comparable<? super AnyType>> void merge(AnyType[] arr, int start, int mid, int end, AnyType[] tmp)

   第一个方法是一个递归方法，对于递归方法，一定要明晰该方法功能的定义，这里这个递归方法的目的就是对传入数组的start到end之间的元素进行排序，而tmp则是一个辅助数组。在该方法的具体实现中，我们可以看到，其思路是首先对start到mid之间的元素继续调用递归进行排序，然后是对mid到end之间的元素调用递归进行排序，经过这两个方法，从start到mid和从mid到end两部分的元素都是经过排序的，此时就需要调用第二个方法。

   第二个方法的功能是对两个已经排序的部分进行合并，对于第一个方法，最后一步执行了第二个方法也即对前面两步排序的部分进行合并之后也就完成了该方法的功能。而对于第二个方法，实现思路和前面描述的一样，分别从两堆牌顶取出较小的一个元素放入临时数组中，当一个牌堆取完之后就将剩下的数组的元素放入第二个牌堆，最后将临时数组的元素放回到原始数组中。

本文主要对归并排序的思想进行了详细的讲解，并且结合具体的代码，结合思想对代码进行了一定的分析。

如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！