歸并排序MergeSort如何實(shí)現(xiàn)自頂向下與自底向上，針對(duì)這個(gè)問(wèn)題，這篇文章詳細(xì)介紹了相對(duì)應(yīng)的分析和解答，希望可以幫助更多想解決這個(gè)問(wèn)題的小伙伴找到更簡(jiǎn)單易行的方法。
商河網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)！從網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開(kāi)發(fā)、APP開(kāi)發(fā)、成都響應(yīng)式網(wǎng)站建設(shè)等網(wǎng)站項(xiàng)目制作，到程序開(kāi)發(fā)，運(yùn)營(yíng)維護(hù)。創(chuàng)新互聯(lián)從2013年創(chuàng)立到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來(lái)保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)。
歸并排序 MergeSort 是在計(jì)算機(jī)上實(shí)現(xiàn)的最早的算法之一， 由馮·諾伊曼 John von Neumann 在 1945 年發(fā)表"101報(bào)告"時(shí)提出，后在 1951 年完成的 EDVAC計(jì)算機(jī)上應(yīng)用了這一算法。
歸并排序是在歸并的基礎(chǔ)上將數(shù)組不斷劃分成子數(shù)組進(jìn)行排序，從而使整個(gè)數(shù)組完全有序，該算法是采用了典型的分治法來(lái)解決問(wèn)題，即先將問(wèn)題分解成子問(wèn)題，再對(duì)子問(wèn)題的解進(jìn)行合并從而得到整個(gè)問(wèn)題的解。
歸并排序的核心思想就在于 并（merging），為了更好的理解歸并排序，我們先來(lái)了解一下原地歸并的概念
新建一個(gè)原始數(shù)組的拷貝作為輔助數(shù)組
使用兩個(gè)指針同時(shí)遍歷輔助數(shù)據(jù)中的兩部分?jǐn)?shù)據(jù)
將兩個(gè)指針指向的較小元素放置到原始數(shù)組中
然后將較小元素的指針往后一位
當(dāng)有一邊數(shù)據(jù)遍歷完成，直接剩下的那部分?jǐn)?shù)據(jù)拷貝到原始數(shù)組中
重慶分公司
重慶分公司
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
assert isSorted(a, lo, mid);
assert isSorted(a, mid + 1, hi);
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++]; // 左邊耗盡，取右半邊數(shù)據(jù)
else if (j > hi) a[k] = aux[i++]; // 右邊耗盡，取左半邊數(shù)據(jù)
else if (less(aux[i], aux[j])) a[k] = aux[j++]; // 取較小值
else a[k] = aux[i++];
}
assert isSorted(a, lo, hi);
}
public static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
public static boolean isSorted(Comparable[] a, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++) {
if (less(a[i], a[i-1])) return false;
}
return true;
}
public static boolean isSorted(Comparable[] a) {
return isSorted(a, 0, a.length - 1);
}這里代碼用到了 assert，順便提一下
我們可以使用斷言來(lái)驗(yàn)證猜想，前面的代碼里我們使用 assert 來(lái)判定輸入?yún)?shù)是否如我們所預(yù)想的那樣已經(jīng)排好序
斷言可以幫助我們檢測(cè)邏輯上的 bug
讓代碼可讀性更強(qiáng)?如果 assert 后面的條件語(yǔ)句不滿足，則會(huì)拋出異常
我們可以加上參數(shù)來(lái)控制異常的拋出，在部署代碼到生產(chǎn)環(huán)境時(shí)禁用斷言，而在本地或者測(cè)試環(huán)境啟用斷言來(lái)幫助我們調(diào)試程序，默認(rèn)是禁用的，我們需要手動(dòng)開(kāi)啟
java -ea MyApplication // 啟用斷言 enable java -da MyApplication // 禁用斷言 disable （默認(rèn)設(shè)置）
如果使用 IDEA 的話在 Application 的 VM Options 中加上 -ea 就可以開(kāi)啟了，不填默認(rèn)是禁用的
歸并過(guò)程完成了，我們有兩種方式可以實(shí)現(xiàn)排序算法
將數(shù)組元素不斷二分，直到子數(shù)組元素只有一個(gè)，然后將兩個(gè)有序的數(shù)組向下合并，再將新的兩個(gè)有序的數(shù)組向下合并，直至整個(gè)數(shù)組有序
我們只需要遞歸的將數(shù)據(jù)不斷分區(qū)合并就可以達(dá)到排序的效果了，代碼如下：
public class MergeSort {
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
/** 見(jiàn)前面歸并部分 */
}
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid + 1, hi);
merge(a, aux, lo, mid, hi);
}
private static void sort(Comparable[] a) {
Comparable[] aux = new Comparable[a.length];
sort(a, aux, 0, a.length - 1);
}
}這里有個(gè)小細(xì)節(jié)，輔助數(shù)組 aux 是在入口的 sort() 方法中初始化的，而不是放在遞歸的方法里，因?yàn)榉旁谶f歸的方法里會(huì)產(chǎn)生很多額外的小數(shù)組，會(huì)導(dǎo)致內(nèi)存比較碎，不利于內(nèi)存的回收整理，而放在外面只需要初始化一個(gè)數(shù)組就可以了，如果你的歸并排序性能比較差一般都是因?yàn)檫@個(gè)引起的
歸并排序是典型的分治思想的實(shí)踐，將問(wèn)題分解成子問(wèn)題，各個(gè)擊破，然后將結(jié)果合并
將數(shù)組中元素一個(gè)個(gè)歸并成兩兩有序的子數(shù)組，再歸并成 2 個(gè)，再歸并成 8 個(gè)直至數(shù)組完全有序
數(shù)組是按照長(zhǎng)度進(jìn)行劃分的，最后子數(shù)組的數(shù)量可能不滿足要求，不能超過(guò)數(shù)據(jù)最大長(zhǎng)度，需要特殊處理一下
private static void sortByBottomUp(Comparable[] a) {
int N = a.length;
Comparable[] aux = new Comparable[N];
for (int size = 1; size < N; size = size + size)
for (int lo = 0; lo < N - size; lo += size + size)
merge(a, aux, lo, lo + size + 1, Math.min(lo + size + size - 1, N - 1));
}歸并排序在數(shù)據(jù)量非常大的情況下性能是很好的，比插入排序快很多
個(gè)人 PC： 10^8 次比較/秒
超級(jí) PC：10^12 次比較/秒
所以一個(gè)好的算法可以強(qiáng)過(guò)超級(jí) PC，簡(jiǎn)而言之可以省錢(qián)
歸并排序的時(shí)間復(fù)雜度為 O(NLgN)，因?yàn)槊看味紝?shù)組分為兩部分，然后進(jìn)行合并
C(N) ≤ C(?N / 2?) + C(?N/ 2?) + N = NLgN
// 證明過(guò)程
D (N) = 2 D (N/2) + N D (N) / N = 2 D (N/2) / N + 1 = D (N/2) / (N/2) + 1 = D (N/4) / (N/4) + 1 + 1 = D (N/8) / (N/8) + 1 + 1 + 1 . . . = D (N/N) / (N/N) + 1 + 1 + ... + 1 = lgN D(N) = NLgN
我們?cè)谂判驎r(shí)借助了一個(gè)與原數(shù)組空間相等的數(shù)組，所以空間復(fù)雜度為 O(N)
歸并排序是穩(wěn)定排序，在排序時(shí)本來(lái)排在前面的元素不會(huì)在排序過(guò)程中調(diào)換到后面，所以是穩(wěn)定排序
歸并排序比較適合大數(shù)組，對(duì)于較小數(shù)組，使用插入排序性能比較好，我們?cè)谧雠判驎r(shí)可以設(shè)置一個(gè)閾值，當(dāng)大于這個(gè)值的時(shí)候我們就使用歸并排序，否則我們使用插入排序，這個(gè)閾值約為 7。 并且我們?cè)诤喜⑶翱梢韵冗M(jìn)行檢測(cè)，如果已經(jīng)是有序的，則可以直接 return 了
代碼實(shí)現(xiàn)
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
if (hi <= lo + CUTOFF - 1) {
Insertion.sort(a, lo, hi);
return;
}
int mid = lo + (hi - lo) / 2;
sort (a, aux, lo, mid);
sort (a, aux, mid+1, hi);
if (!less(a[mid+1], a[mid])) return; // 有序則直接 return
merge(a, aux, lo, mid, hi);
}Java 集合類中提供的排序方法 Collections.sort() 也是復(fù)合實(shí)現(xiàn)，在數(shù)據(jù)量小的時(shí)候使用插入排序，里面的閾值是 32，但是它實(shí)現(xiàn)的插入排序方法有優(yōu)化過(guò)，是二分插入排序
感興趣的同學(xué)可以看看 Collections.sort() 方法的源碼，里面涉及到了各種不同的排序算法
關(guān)于歸并排序MergeSort如何實(shí)現(xiàn)自頂向下與自底向上問(wèn)題的解答就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，如果你還有很多疑惑沒(méi)有解開(kāi)，可以關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道了解更多相關(guān)知識(shí)。
