Java實作歸併排序演算法的方法實例詳解

這篇文章主要介紹了java 中歸併排序演算法詳解的相關資料,歸併排序演算法又稱為合併排序演算法，是一種時間複雜度為O(N logN)的排序演算法，因而其在平常生活工作中應用非常廣泛，需要的朋友可以參考下

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兩部分的元素都是經過排序的，此時就需要呼叫第二個方法。

        第二個方法的功能是合併兩個已排序的部分#，對於第一個方法，最後一步執行了第二個方法也即對前面兩步驟排序的部分進行合併之後也就完成了此方法的功能。而對於第二個方法，實現想法和前面描述的一樣，分別從兩堆牌頂取出較小的一個元素放入臨時數組中，當一個牌堆取完之後就將剩下的數組的元素放入第二個牌堆，最後將臨時數組的元素放回原始數組。

       本文主要對歸併排序的想法進行了詳細的解釋，並且結合特定的程式碼，結合思想對程式碼進行了一定的分析。

以上是Java實作歸併排序演算法的方法實例詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！