java 算法之歸并排序詳解及實(shí)現(xiàn)代碼
java 算法之歸并排序詳解
一、思想
歸并排序:將一個(gè)數(shù)組排序,可以先(遞歸地)將它分成兩半部份分別排序,然后將結(jié)果歸并起來;
二、概念
歸并:將兩個(gè)有序的數(shù)組歸并成一個(gè)更大的有序數(shù)組;
三、特點(diǎn)
優(yōu)點(diǎn):能夠保證將任意長(zhǎng)度為N的數(shù)組排序所需要的時(shí)間和NlogN成正比;
缺點(diǎn):需要額外的空間和N成正比;
四、實(shí)現(xiàn)方法
將兩個(gè)不同的有序數(shù)組歸并到第三個(gè)數(shù)組中;
先將前半部分排序,在將后半部分排序,然后在數(shù)組中移動(dòng)元素而不需要使用額外的空間;
五、代碼
/** * 歸并排序 * * @author pengcx * */ public class Merge extends Sort { /** 歸并所需的輔助數(shù)組 */ private static Comparable[] aux; public static void main(String[] args) { String[] a = { "d", "a", "w", "b", "q" }; Merge.sort(a); show(a); } public static void sort(Comparable[] a) { aux = new Comparable[a.length]; sort(a, 0, a.length - 1); } /** * 排序數(shù)組的a[lo]至a[hi]元素 * * @param a * 數(shù)組a * @param lo * 最小元素位置lo * @param hi * 最大元素位置hi */ private static void sort(Comparable[] a, int lo, int hi) { if (hi <= lo) { return; } // 計(jì)算數(shù)組中間位置 int mid = lo + (hi - lo) / 2; // 排序數(shù)組a左邊的元素 sort(a, lo, mid); // 排序數(shù)組a右邊的元素 sort(a, mid + 1, hi); // 合并數(shù)組a左邊和右邊的元素 merge(a, lo, mid, hi); } /** * 將數(shù)組a的a[lo]至a[mid]的元素與a[mid]至a[hi]的元素合并 * * @param a * 合并的數(shù)組a * @param lo * 最小數(shù)組元素lo * @param mid * 中間元素位置mid * @param hi * 最大元素位置hi */ public static void merge(Comparable[] a, int lo, int mid, int hi) { int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) { aux[k] = a[k]; } for (int k = lo; k <= hi; k++) { // 如果左邊的元素用盡,取右邊的元素 if (i > mid) { a[k] = aux[j++]; } // 如果右邊的元素用盡,取左邊的元素 else if (j > hi) { a[k] = aux[i++]; } // 如果右半邊的當(dāng)前元素小于左半邊的當(dāng)前元素,取右半邊元素 else if (less(aux[j], aux[i])) { a[k] = aux[j++]; } // 如果右半邊的當(dāng)前元素大于等于左半邊的當(dāng)前元素,取左半邊元素 else { a[k] = aux[i++]; } } } }
感謝閱讀,希望能幫助到大家,謝謝大家對(duì)本站的支持!
相關(guān)文章
Java導(dǎo)入新項(xiàng)目報(bào)錯(cuò)java:JDK?isn‘t?specified?for?module解決辦法
這篇文章主要給大家介紹了關(guān)于Java導(dǎo)入新項(xiàng)目報(bào)錯(cuò)java:JDK?isn‘t?specified?for?module的解決辦法,當(dāng)您在導(dǎo)入Java項(xiàng)目時(shí)遇到錯(cuò)誤時(shí),可以嘗試以下面的方法來處理,需要的朋友可以參考下2024-05-05SpringBoot項(xiàng)目中連接Gauss數(shù)據(jù)庫
本文主要介紹了SpringBoot項(xiàng)目中連接Gauss數(shù)據(jù)庫,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-06-06詳解spring cloud分布式整合zipkin的鏈路跟蹤
這篇文章主要介紹了詳解spring cloud分布式整合zipkin的鏈路跟蹤,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-07-07Java?LocalTime的常用時(shí)間操作總結(jié)
日常開發(fā)中,?我們會(huì)經(jīng)常遇到時(shí)間的運(yùn)算,?操作,?格式化等,?這篇文章主要為大家詳細(xì)介紹了LocalTime的常用時(shí)間操作,感興趣的小伙伴可以了解一下2023-11-11單機(jī)redis分布式鎖實(shí)現(xiàn)原理解析
這篇文章主要介紹了單機(jī)redis分布式鎖實(shí)現(xiàn)原理解析,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-04-04java Hibernate 一對(duì)多自身關(guān)聯(lián)問題
formBean在提交表單的時(shí)候,域中數(shù)據(jù)庫在下一次中仍然保留引起的,struts formBean 默認(rèn)的scope為session,手動(dòng)設(shè)置為request,就好了2008-07-07