怎么在java 項(xiàng)目中使用歸并排序算法

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

歸并排序

       歸并排序，指的是將兩個(gè)已經(jīng)排序的序列合并成一個(gè)序列的操作。 

歸并操作的過(guò)程如下：

•  申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列

•  設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置

•  比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置

•  重復(fù)步驟3直到某一指針到達(dá)序列尾

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

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++]; 
 
  //考回原數(shù)組,此處最好用System.arraycopy優(yōu)化 
  for (int i = 0; i < numElements; i++, rightEnd--) 
    ts[rightEnd] = tempArray[rightEnd]; 
}

 復(fù)雜度：O(n log n)

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

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

 穩(wěn)定性：穩(wěn)定 

擴(kuò)展：

       在java中，當(dāng)執(zhí)行一次泛型排序時(shí)，進(jìn)行一次元比較可能是昂貴的，但是移動(dòng)元素則是省時(shí)間的。歸并排序使用所有的流行的排序算法中最少的比較次數(shù)，因此是使用java的通用排序算中的上好的選擇。

看完上述內(nèi)容是否對(duì)您有幫助呢？如果還想對(duì)相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章，請(qǐng)關(guān)注億速云行業(yè)資訊頻道，感謝您對(duì)億速云的支持。