java實(shí)現(xiàn)歸并排序算法
更新時(shí)間：2015年04月09日 11:21:02 投稿：hebedich
歸并排序：是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。 本文我們就來(lái)詳細(xì)的探討下。
歸并排序算法思想:
分而治之(divide - conquer);每個(gè)遞歸過(guò)程涉及三個(gè)步驟
第一, 分解: 把待排序的 n 個(gè)元素的序列分解成兩個(gè)子序列, 每個(gè)子序列包括 n/2 個(gè)元素.
第二, 治理: 對(duì)每個(gè)子序列分別調(diào)用歸并排序MergeSort, 進(jìn)行遞歸操作
第三, 合并: 合并兩個(gè)排好序的子序列,生成排序結(jié)果.
public static void mergeSort(int[] a, int[] tmp, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(a, tmp, left, mid);// 左排序
mergeSort(a, tmp, mid + 1, right);// 右排序
merge(a, tmp, left, mid + 1, right);// 左右合并
}
}
public static void merge(int[] a, int[] tmp, int left, int rightPos,
int right) {
int leftEnd = rightPos - 1;
int tmpPos = left;
int num = right - left + 1;
while (left <= leftEnd && rightPos <= right) {
if (a[left] < a[rightPos]) {
tmp[tmpPos++] = a[left++];
} else {
tmp[tmpPos++] = a[rightPos++];
}
}
while (left <= leftEnd) {
tmp[tmpPos++] = a[left++];
}
while (rightPos <= right) {
tmp[tmpPos++] = a[rightPos++];
}
for (int i = 0; i < num; i++, right--) {
a[right] = tmp[right];
}
}
歸并算法示意圖：
以上所述就是本文的全部?jī)?nèi)容了，希望大家能夠喜歡。
相關(guān)文章
SpringAOP如何修改請(qǐng)求參數(shù)列表
這篇文章主要介紹了SpringAOP如何修改請(qǐng)求參數(shù)列表問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-03-03
這篇文章主要給大家介紹了關(guān)于java中Websocket的使用方法,WebSocket是HTML5開(kāi)始提供的一種在瀏覽器和服務(wù)器間進(jìn)行全雙工通信的協(xié)議,文中通過(guò)代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-11-11
Flink實(shí)現(xiàn)特定統(tǒng)計(jì)的歸約聚合reduce操作
這篇文章主要介紹了Flink實(shí)現(xiàn)特定統(tǒng)計(jì)的歸約聚合reduce操作，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧2023-02-02
這篇文章主要介紹了Java中的HashMap源碼解析,當(dāng)HashMap中的其中一個(gè)鏈表的對(duì)象個(gè)數(shù)如果達(dá)到了8個(gè),此時(shí)如果數(shù)組長(zhǎng)度沒(méi)有達(dá)到64,那么HashMap會(huì)先擴(kuò)容解決,如果已經(jīng)達(dá)到了64,那么這個(gè)鏈表會(huì)變成紅黑樹(shù),需要的朋友可以參考下2023-12-12
java之向linux文件夾下寫(xiě)文件無(wú)權(quán)限的問(wèn)題
這篇文章主要介紹了java之向linux文件夾下寫(xiě)文件無(wú)權(quán)限的問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-09-09
JPA findById方法和getOne方法的區(qū)別說(shuō)明
這篇文章主要介紹了JPA findById方法和getOne方法的區(qū)別，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教。2021-08-08
這篇文章主要介紹了在Java編程中定義方法,是Java入門(mén)學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-10-10
這篇文章主要介紹了javascript最新2020經(jīng)典面試題的相關(guān)內(nèi)容，有需要的朋友們可以學(xué)習(xí)下。2020-02-02
XSS攻擊全稱(chēng)跨站腳本攻擊，是一種在web應(yīng)用中的計(jì)算機(jī)安全漏洞，允許惡意web用戶(hù)將代碼植入到提供給其它用戶(hù)使用的頁(yè)面中。本文介紹防止XSS攻擊的方法2021-06-06
spring boot使用自定義配置的線程池執(zhí)行Async異步任務(wù)
這篇文章主要介紹了spring boot使用自定義配置的線程池執(zhí)行Async異步任務(wù)，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-01-01