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