利用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 > void mergeSort(AnyType[] arr) {
  AnyType[] tmp = ((AnyType[]) new Comparable[arr.length]);
  mergeSort(arr, 0, arr.length - 1, tmp);
 }

 private static > 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 > 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];
  }
 }
}