java 歸并排序的實(shí)例詳解

更新時(shí)間：2017年07月14日 09:34:43 投稿：lqh

這篇文章主要介紹了java 歸并排序的實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下

java 歸并排序的實(shí)例詳解

歸并排序

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

歸并操作的過程如下：

申請空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列
設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
比較兩個(gè)指針?biāo)赶虻脑兀x擇相對小的元素放入到合并空間，并移動指針到下一位置
重復(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)行一次元比較可能是昂貴的，但是移動元素則是省時(shí)間的。歸并排序使用所有的流行的排序算法中最少的比較次數(shù)，因此是使用java的通用排序算中的上好的選擇。

以上使用java 使用歸并排序的簡單實(shí)例，有關(guān)java算法知識本站還有很多，大家可以搜索，感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

您可能感興趣的文章:

相關(guān)文章

mybatisplus根據(jù)條件只更新一個(gè)字段的實(shí)現(xiàn)
MyBatis-Plus提供使用update方法結(jié)合Wrapper來指定更新條件和要更新的字段,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2024-12-12
Java之Runnable啟動線程的使用方式
這篇文章主要介紹了Java之Runnable啟動線程的使用方式,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
2024-01-01
executor包執(zhí)行器功能
這篇文章主要介紹了executor包執(zhí)行器功能,executor包中的各個(gè)子包提供的功能，最終這些功能都由Executor接口及其實(shí)現(xiàn)類共同對外提供服務(wù)。下文介紹該執(zhí)行功能，具有一定的參考價(jià)值，需要的朋友可以考一下
2022-02-02
Spring中配置ContextLoaderListener方式
這篇文章主要介紹了Spring中配置ContextLoaderListener方式,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
2025-04-04
java案例實(shí)戰(zhàn)之字符串轉(zhuǎn)換為二進(jìn)制
最近遇到個(gè)需求,要求編寫一個(gè)程序,從鍵盤錄入一個(gè)字符串,將字符串轉(zhuǎn)換為二進(jìn)制數(shù),下面這篇文章主要給大家介紹了關(guān)于java字符串轉(zhuǎn)換為二進(jìn)制的相關(guān)資料,需要的朋友可以參考下
2023-06-06
Springboot事務(wù)失效的幾種情況解讀
這篇文章主要介紹了Springboot事務(wù)失效的幾種情況解讀,因?yàn)镾pring AOP默認(rèn)使用動態(tài)代理,會給被代理的類生成一個(gè)代理類,事務(wù)相關(guān)的操作都通過代理來完成,使用內(nèi)部方法調(diào)用時(shí),使用的是實(shí)例調(diào)用,沒有通過代理類調(diào)用方法,因此事務(wù)不會檢測到失敗,需要的朋友可以參考下
2023-10-10
Java實(shí)現(xiàn)的n階曲線擬合功能示例
這篇文章主要介紹了Java實(shí)現(xiàn)的n階曲線擬合功能,結(jié)合實(shí)例形式分析了Java基于矩陣的多項(xiàng)式曲線擬合相關(guān)操作技巧,需要的朋友可以參考下
2018-01-01
使用Spring?Boot?2.x構(gòu)建Web服務(wù)的詳細(xì)代碼
這篇文章主要介紹了使用Spring?Boot?2.x構(gòu)建Web服務(wù)的詳細(xì)代碼,主要基于JWT的身份認(rèn)證，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
2022-03-03
springboot使JUL實(shí)現(xiàn)日志管理功能
這篇文章主要介紹了springboot使JUL實(shí)現(xiàn)日志管理功能,本文分步驟給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
2020-09-09
Java Metrics系統(tǒng)性能監(jiān)控工具的使用詳解
Metrics是一個(gè)Java庫，可以對系統(tǒng)進(jìn)行監(jiān)控，統(tǒng)計(jì)一些系統(tǒng)的性能指標(biāo)。本文就來和大家詳細(xì)聊聊這個(gè)工具的具體使用，希望對大家有所幫助
2022-11-11