java 中歸并排序算法詳解

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

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

       從圖中可以看出，對(duì)于兩個(gè)相鄰的整體A和B，其內(nèi)的元素都是按升序排序的，現(xiàn)在有一個(gè)臨時(shí)數(shù)組C，然后對(duì)A和B頂部的兩個(gè)元素進(jìn)行比較，取出較小的一個(gè)元素放入C中，對(duì)于取出元素的整體，其指向元素的下標(biāo)下移一位，繼續(xù)取出兩個(gè)整體中頂部元素較小的一個(gè)放入C中，依次循環(huán)，當(dāng)某個(gè)整體元素取完之后直接將另一個(gè)整體的元素都移入C中。對(duì)于C這個(gè)整體，其就是經(jīng)過(guò)A和B排序而得到的，由于A和B是相鄰的兩個(gè)整體，因而，最后只需要將C中的元素復(fù)制到A和B組成的一個(gè)共同整體中即可，這樣也就達(dá)到了將A和B合并的同時(shí)進(jìn)行排序的目的。

       以下是歸并排序的具體算法：

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

       代碼中主要有兩個(gè)方法

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)

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

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

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

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

最新評(píng)論