java實(shí)現(xiàn)歸并排序算法
更新時(shí)間：2015年04月09日 11:21:02 投稿：hebedich
歸并排序：是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。 本文我們就來詳細(xì)的探討下。
歸并排序算法思想:
分而治之(divide - conquer);每個(gè)遞歸過程涉及三個(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)文章
使用IDEA創(chuàng)建一個(gè)vert.x項(xiàng)目的方法
這篇文章主要介紹了使用IDEA創(chuàng)建一個(gè)vert.x項(xiàng)目的方法，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-09-09
response.sendRedirect()實(shí)現(xiàn)重定向(頁(yè)面跳轉(zhuǎn))
在Java web開發(fā)中，使用response.sendRedirect()可實(shí)現(xiàn)重定向功能。本文將介紹如何使用該方法進(jìn)行頁(yè)面跳轉(zhuǎn)，以及該方法的使用場(chǎng)景和注意事項(xiàng)，感興趣的可以了解一下2023-04-04
spring中BeanPostProcessor的作用和使用注意事項(xiàng)
在Spring框架中,BeanPostProcessor?是一個(gè)核心擴(kuò)展接口,允許你在Bean實(shí)例化的過程中插入自定義邏輯,本文給大家介紹spring中BeanPostProcessor的作用,感興趣的朋友一起看看吧2025-04-04
SpringBoot之RestTemplate在URL中轉(zhuǎn)義字符的問題
這篇文章主要介紹了SpringBoot之RestTemplate在URL中轉(zhuǎn)義字符的問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-06-06
SpringBoot通過源碼探究靜態(tài)資源的映射規(guī)則實(shí)現(xiàn)
這篇文章主要介紹了SpringBoot通過源碼探究靜態(tài)資源的映射規(guī)則實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-05-05
這篇文章主要介紹了IDEA 阿里JAVA規(guī)范插件的具體使用，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08
Java通過接口實(shí)現(xiàn)匿名類的實(shí)例代碼
這篇文章介紹了Java通過接口實(shí)現(xiàn)匿名類的實(shí)例代碼，有需要的朋友可以參考一下2013-10-10
Java利用httpclient通過get、post方式調(diào)用https接口的方法
這篇文章主要介紹了Java利用httpclient通過get、post方式調(diào)用https接口的方法,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-02-02
Java中位運(yùn)算(移位、位與、或、異或、非） 的簡(jiǎn)單實(shí)例
Java中位運(yùn)算(移位、位與、或、異或、非） 的簡(jiǎn)單實(shí)例，需要的朋友可以參考一下2013-02-02
spring boot validation參數(shù)校驗(yàn)實(shí)例分析
這篇文章主要介紹了spring boot validation參數(shù)校驗(yàn),結(jié)合實(shí)例形式分析了spring boot validation進(jìn)行數(shù)據(jù)有效性驗(yàn)證的相關(guān)操作技巧,需要的朋友可以參考下2019-11-11