怎么在java 項目中使用歸并排序算法

怎么在java 項目中使用歸并排序算法？很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。

歸并排序

       歸并排序，指的是將兩個已經排序的序列合并成一個序列的操作。 

歸并操作的過程如下：

•  申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列

•  設定兩個指針，最初位置分別為兩個已經排序序列的起始位置

•  比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置

•  重復步驟3直到某一指針到達序列尾

•  將另一序列剩下的所有元素直接復制到合并序列尾
  

Java代碼 

/** 
 * 歸并排序 
 * 
 * @param ts 
 */ 
@SuppressWarnings("unchecked") 
public static <T extends Comparable<? super T>> void mergeSort(T[] ts) { 
 
  // 輔助空間 
  T[] tempArray = (T[]) new Comparable[ts.length]; 
 
  mergeSort(ts, tempArray, 0, ts.length - 1); 
} 
 
/** 
 * 遞歸 
 */ 
private static <T extends Comparable<? super T>> void mergeSort(T[] ts, T[] tempArray, int left, int right) { 
 
  if (left < right) { 
 
    int center = (left + right) / 2; 
 
    mergeSort(ts, tempArray, left, center); 
 
    mergeSort(ts, tempArray, center + 1, right); 
 
    // 左右合并 
    merge(ts, tempArray, left, center + 1, right); 
 
  } 
 
} 
 
/** 
 * 合并 
 */ 
private static <T extends Comparable<? super T>> void merge(T[] ts, T[] tempArray, int leftPos, int rightPos, int rightEnd) { 
  int leftEnd = rightPos - 1; 
  int temPos = leftPos; 
  int numElements = rightEnd - leftPos + 1; 
 
  while (leftPos <= leftEnd && rightPos <= rightEnd) 
    //比較放到輔助空間 
    if (ts[leftPos].compareTo(ts[rightPos]) <= 0) 
      tempArray[temPos++] = ts[leftPos++]; 
    else 
      tempArray[temPos++] = ts[rightPos++]; 
 
  while (leftPos <= leftEnd) 
    tempArray[temPos++] = ts[leftPos++]; 
 
  while (rightPos <= rightEnd) 
    tempArray[temPos++] = ts[rightPos++]; 
 
  //考回原數組,此處最好用System.arraycopy優化 
  for (int i = 0; i < numElements; i++, rightEnd--) 
    ts[rightEnd] = tempArray[rightEnd]; 
}

 復雜度：O(n log n)

       比較操作的次數介于(n log n)/2和n log n - n + 1。 賦值操作的次數是(2nlogn)。

       歸并算法的空間復雜度為：Θ(n) 

 穩定性：穩定 

擴展：

       在java中，當執行一次泛型排序時，進行一次元比較可能是昂貴的，但是移動元素則是省時間的。歸并排序使用所有的流行的排序算法中最少的比較次數，因此是使用java的通用排序算中的上好的選擇。

看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。