java 中歸并排序算法詳解

 歸并排序算法，顧名思義，是一種先分再合的算法，其算法思想是將要排序的數(shù)組分解為單個的元素，每個元素就是一個單個的個體，然后將相鄰的兩個元素進行從小到大或從大到小的順序排序組成一個整體，每個整體包含一到兩個元素，然后對相鄰的整體繼續(xù)“合”并，因為每個整體都是排過序的，因而可以采用一定的算法對其進行合并，合并之后每個整體包含三到四個元素，繼續(xù)對相鄰的整體進行合并，直到所有的整體都合并為一個整體，最終得到的整體就是將原數(shù)組進行排序之后的結(jié)果。

       對于相鄰的整體，其合并的思想是每次都取兩個整體（假設(shè)其實按升序排序的）中最小的元素放到一個新數(shù)組中，依次循環(huán)，最終兩個整體中的元素都被取完即可得到一個按升序排序的整體。該合并過程就像有兩個升序排序的牌堆A和B（如圖所示），每次從最頂上取出一個元素放到牌堆C中：

       從圖中可以看出，對于兩個相鄰的整體A和B，其內(nèi)的元素都是按升序排序的，現(xiàn)在有一個臨時數(shù)組C，然后對A和B頂部的兩個元素進行比較，取出較小的一個元素放入C中，對于取出元素的整體，其指向元素的下標下移一位，繼續(xù)取出兩個整體中頂部元素較小的一個放入C中，依次循環(huán)，當某個整體元素取完之后直接將另一個整體的元素都移入C中。對于C這個整體，其就是經(jīng)過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)

       第一個方法是一個遞歸方法，對于遞歸方法，一定要明晰該方法功能的定義，這里這個遞歸方法的目的就是對傳入數(shù)組的start到end之間的元素進行排序，而tmp則是一個輔助數(shù)組。在該方法的具體實現(xiàn)中，我們可以看到，其思路是首先對start到mid之間的元素繼續(xù)調(diào)用遞歸進行排序，然后是對mid到end之間的元素調(diào)用遞歸進行排序，經(jīng)過這兩個方法，從start到mid和從mid到end兩部分的元素都是經(jīng)過排序的，此時就需要調(diào)用第二個方法。

        第二個方法的功能是對兩個已經(jīng)排序的部分進行合并，對于第一個方法，最后一步執(zhí)行了第二個方法也即對前面兩步排序的部分進行合并之后也就完成了該方法的功能。而對于第二個方法，實現(xiàn)思路和前面描述的一樣，分別從兩堆牌頂取出較小的一個元素放入臨時數(shù)組中，當一個牌堆取完之后就將剩下的數(shù)組的元素放入第二個牌堆，最后將臨時數(shù)組的元素放回到原始數(shù)組中。

       本文主要對歸并排序的思想進行了詳細的講解，并且結(jié)合具體的代碼，結(jié)合思想對代碼進行了一定的分析。

如有疑問請留言或者到本站社區(qū)交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

最新評論