死磕歸并排序算法
?本文已被Github倉庫收錄 https://github.com/silently9527/JavaCore
程序員常用的IDEA插件：https://github.com/silently9527/ToolsetIdeaPlugin
完全開源的淘客項(xiàng)目：https://github.com/silently9527/mall-coupons-server
微信公眾號：貝塔學(xué)Java
?
前言
在上一篇《常見的初級排序算法，這次全搞懂》，主要談了常用的初級算法，這些算法的時間復(fù)雜度都是O(n2)，這些算法無法處理大量數(shù)據(jù)；本篇我們談一種基于歸并操作完成排序的算法。
歸并排序算法思路
要將一個數(shù)組排序，可以先將數(shù)組分為兩個數(shù)組分別排序，然后再將結(jié)果歸并在一起，重復(fù)遞歸這個過程，直到數(shù)組整體有序，這就是歸并排序的算法思路。
歸并排序的優(yōu)點(diǎn)是它能夠保證任意長度為N的數(shù)組排序所需的時間與 NlogN 成正比，這個優(yōu)點(diǎn)是初級排序無法達(dá)到的。
缺點(diǎn)是因?yàn)闅w并操作需要引入額外的數(shù)組，額外的空間與N成正比
原地歸并實(shí)現(xiàn)
在實(shí)現(xiàn)歸并排序之前，我們需要先完成兩個有序數(shù)組的歸并操作，即將兩個有序的數(shù)組合并成一個有序的數(shù)組；
在此過程中我們需要引入一個輔助數(shù)組； 定義的方法簽名為merge(a, lo, mid, hi)，這個方法將數(shù)組a[lo..mid]與a[mid..hi]歸并成一個有序的數(shù)組，結(jié)果存放到a[lo..mid]中； 該方法中需要使用的上一篇中的公共函數(shù) less，參考上一篇文章《常見的初級排序算法，這次全搞懂》
public class MergeSort implements SortTemplate {
private Comparable[] aux;
@Override
public void sort(Comparable[] array) {
//待實(shí)現(xiàn)
}
private void merge(Comparable[] a, int lo, int mid, int hi) {
for (int i = lo; i <= hi; i++) {
aux[i] = a[i];
}
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) {
a[k] = aux[j++];
} else if (j > hi) {
a[k] = aux[i++];
} else if (less(aux[i], aux[j])) {
a[k] = aux[i++];
} else {
a[k] = aux[j++];
}
}
}
}
自頂向下的歸并排序
基于分而治之的思想，大的數(shù)組排序，先遞歸拆分成小的數(shù)組，保證小的數(shù)組有序再歸并，直到整個數(shù)組有序，這個操作就是自頂向下的歸并排序
public class MergeSort implements SortTemplate {
private Comparable[] aux;
@Override
public void sort(Comparable[] array) {
aux = new Comparable[array.length];
doSort(array, 0, array.length - 1);
}
private void doSort(Comparable[] array, int lo, int hi) {
if (lo >= hi) {
return;
}
int mid = (hi - lo) / 2 + lo;
doSort(array, lo, mid);
doSort(array, mid + 1, hi);
merge(array, lo, mid, hi);
}
private void merge(Comparable[] a, int lo, int mid, int hi) {
//省略
}
}
以上代碼是標(biāo)準(zhǔn)的遞歸歸并排序操作，但是經(jīng)過仔細(xì)思考之后，該算法還有可以優(yōu)化的地方
「測試數(shù)組是否已經(jīng)有序」；如果a[mid]<=a[mid+1]，那么我們就可以跳過merge方法，減少merge操作；修復(fù)之后的doSort方法
private void doSort(Comparable[] array, int lo, int hi) {
if (lo >= hi) {
return;
}
int mid = (hi - lo) / 2 + lo;
doSort(array, lo, mid);
doSort(array, mid + 1, hi);
if (array[mid].compareTo(array[mid + 1]) >= 0) {
merge(array, lo, mid, hi);
}
}
「對于小規(guī)模的數(shù)組可以是用插入排序」；對于小規(guī)模的數(shù)組使用歸并排序會增加遞歸調(diào)用棧，所以我們可以考慮使用插入排序來處理子數(shù)組的排序
private void doSort(Comparable[] array, int lo, int hi) {
if (lo >= hi) {
return;
}
if (hi - lo < 5) { //測試，小于5就使用插入排序
insertionSort(array, lo, hi);
return;
}
int mid = (hi - lo) / 2 + lo;
doSort(array, lo, mid);
doSort(array, mid + 1, hi);
if (less(array[mid + 1], array[mid])) {
merge(array, lo, mid, hi);
}
}
//插入排序
private void insertionSort(Comparable[] array, int lo, int hi) {
for (int i = lo; i <= hi; i++) {
for (int j = i; j > lo && less(array[j], array[j - 1]); j--) {
exch(array, j, j - 1);
}
}
}
「節(jié)省復(fù)制元素到輔助數(shù)組的時間」；要實(shí)現(xiàn)該操作較麻煩，需要在每一層遞歸的時候交換輸入數(shù)據(jù)和輸出數(shù)組的角色；修改之后的完整代碼如下：
public class MergeSort implements SortTemplate {
private Comparable[] aux;
@Override
public void sort(Comparable[] array) {
aux = array.clone();
doSort(aux, array, 0, array.length - 1);
}
private void doSort(Comparable[] src, Comparable[] dest, int lo, int hi) {
if (lo >= hi) {
return;
}
if (hi - lo < 5) { //測試，小于5就使用插入排序
insertionSort(dest, lo, hi);
return;
}
int mid = (hi - lo) / 2 + lo;
doSort(dest, src, lo, mid);
doSort(dest, src, mid + 1, hi);
if (less(src[mid + 1], src[mid])) {
merge(src, dest, lo, mid, hi);
}
}
//插入排序
private void insertionSort(Comparable[] array, int lo, int hi) {
for (int i = lo; i <= hi; i++) {
for (int j = i; j > lo && less(array[j], array[j - 1]); j--) {
exch(array, j, j - 1);
}
}
}
private void merge(Comparable[] src, Comparable[] dest, int lo, int mid, int hi) {
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) {
dest[k] = src[j++];
} else if (j > hi) {
dest[k] = src[i++];
} else if (less(src[i], src[j])) {
dest[k] = src[i++];
} else {
dest[k] = src[j++];
}
}
}
}
每一層遞歸操作都會讓子數(shù)組有序，但是子數(shù)組可能是aux[lo..hi]也有可能是a[lo..hi]；由于第一次調(diào)用doSort傳入的是src=aux，dest=array，所以遞歸最后的結(jié)果一定是輸入到了array中，保證了array整體排序完成
自底向上的歸并排序
實(shí)現(xiàn)歸并算法還有另一種思路，就是先歸并哪些小的數(shù)組，然后再成對歸并得到子數(shù)組，直到整個數(shù)組有序
public class MergeSort implements SortTemplate {
private Comparable[] aux;
@Override
public void sort(Comparable[] array) {
int length = array.length;
aux = new Comparable[length];
for (int sz = 1; sz < length; sz += sz) {
for (int i = 0; i < length - sz; i += 2 * sz) {
merge(array, i, i + sz - 1, Math.min(i + 2 * sz - 1, length - 1));
}
}
}
private void merge(Comparable[] a, int lo, int mid, int hi) {
for (int i = lo; i <= hi; i++) {
aux[i] = a[i];
}
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) {
a[k] = aux[j++];
} else if (j > hi) {
a[k] = aux[i++];
} else if (less(aux[i], aux[j])) {
a[k] = aux[i++];
} else {
a[k] = aux[j++];
}
}
}
}
最后（點(diǎn)關(guān)注，不迷路）
文中或許會存在或多或少的不足、錯誤之處，有建議或者意見也非常歡迎大家在評論交流。
最后，「寫作不易，請不要白嫖我喲」，希望朋友們可以「點(diǎn)贊評論關(guān)注」三連，因?yàn)檫@些就是我分享的全部動力來源??
?文中所有源碼已放入到了github倉庫https://github.com/silently9527/JavaCore
?