版權(quán)聲明：本文源自簡(jiǎn)書(shū)tianma逞泄，轉(zhuǎn)載請(qǐng)務(wù)必注明出處：http://www.reibang.com/p/df8a9e136295
概念
歸并排序就是利用歸并的思想實(shí)現(xiàn)的排序算法石窑。歸并排序的原理：假設(shè)初始序列含有n個(gè)記錄，該序列可以看成n個(gè)有序的子序列神帅，其中每個(gè)子序列的長(zhǎng)度為1讹俊，然后兩兩歸并牵啦，得到?n/2?（?x?表示不小于x的最小整數(shù)）個(gè)長(zhǎng)度為2或者1的子序列迫皱，然后再兩兩歸并，……昙沦，如此重復(fù)直到得到1個(gè)長(zhǎng)度為n的有序序列為止琢唾。
遞歸式歸并
演示
比如我們待排序的數(shù)組是 {9, 1, 5, 8, 3, 7, 4, 6, 2}，那么遞歸式的歸并排序?yàn)榱鞒虨椋?/p>
[9, 1, 5, 8, 3, 7, 4, 6, 2]
↓ ↓
[9, 1, 5, 8, 3] [7, 4, 6, 2]
↓ ↓ ↓ ↓
[9, 1, 5] [8, 3] [7, 4] [6, 2]
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
[9, 1] [5] [8] [3] [7] [4] [6] [2]
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
[9] [1] [5] [8] [3] [7] [4] [6] [2] // 上面為拆分盾饮，下面為歸并(合并)
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
[1, 9] [5] [8] [3] [7] [4] [6] [2]
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
[1, 5, 9] [3, 8] [4, 7] [2, 6]
↓ ↓ ↓ ↓
[1, 3, 5, 9, 8] [2, 4, 6, 7]
↓ ↓
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Java實(shí)現(xiàn)
// 定義接口
interface Sorter {
/**
* 將數(shù)組按升序排序
*/
int[] sort(int[] arr);
/**
* 交換數(shù)組arr中的第i個(gè)位置和第j個(gè)位置的關(guān)鍵字
*/
default void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
// 遞歸式歸并排序
class MergeSorter implements Sorter {
@Override
public int[] sort(int[] arr) {
int[] result = new int[arr.length];
mergeSort(arr, result, 0, arr.length - 1);
return result;
}
/**
* 將亂序的src[start...end]歸并排序?yàn)橛行虻膁es[start...end]
*
* @param src
* 歸并前亂序數(shù)組
* @param des
* 歸并后的有序數(shù)組
* @param start
* 歸并的起始位置
* @param end
* 歸并的終止位置
*/
private void mergeSort(int[] src, int[] des, int start, int end) {
if (start == end) {
des[start] = src[start];
return;
}
int[] tmp = new int[src.length];
// 將src[start...end]分為src[start...mid]和src[mid+1...end]兩部分
int mid = (start + end) / 2;
mergeSort(src, tmp, start, mid); // 遞歸采桃，將src[start...mid]歸并為有序的tmp[start...mid]
mergeSort(src, tmp, mid + 1, end); // 遞歸，將src[mid+1...end]歸并為有序的tmp[mid+1...end]
// 將有序的tmp[start...mid]和tmp[mid+1...end]合并為des[start...end]
merge(tmp, des, start, mid, end);
}
/**
* 將有序的src[start, mid]和有序的src[mid+1, end]合并為有序的des[start,end];
* src可能為亂序數(shù)組,但是src[start, mid]和src[mid+1, end]是有序的丘损。
*
* @param src
* 亂序的原數(shù)組
* @param des
* 有序的目標(biāo)數(shù)組
* @param start
* 數(shù)組第一部分起始位置
* @param mid
* 數(shù)組第一部分結(jié)束位置（兩部分的分界點(diǎn)）
* @param end
* 數(shù)組第二部分結(jié)束位置
*/
protected void merge(int[] src, int[] des, int start, int mid, int end) {
int i; // src數(shù)組第一部分下標(biāo)
int j; // src數(shù)組第二部分下標(biāo)
int k; // des數(shù)組下標(biāo)
// 將較小的數(shù)依次移動(dòng)到目標(biāo)數(shù)組中
for (i = start, k = start, j = mid + 1; i <= mid && j <= end;) {
if (src[i] < src[j]) {
des[k] = src[i++];
} else {
des[k] = src[j++];
}
k++;
}
// 將剩余的src[i...mid]復(fù)制到des數(shù)組中
for (; i <= mid; i++) {
des[k] = src[i];
k++;
}
// 將剩余的src[j...end]復(fù)制到des數(shù)組中
for (; j <= end; j++) {
des[k] = src[j];
k++;
}
}
}
復(fù)雜度
時(shí)間復(fù)雜度：
因?yàn)闅w并的遞歸操作其實(shí)就是二叉樹(shù)的結(jié)構(gòu)普办，故而，最好情況 = 最壞情況 = 平均情況 = O(nlogn)
空間復(fù)雜度：
因?yàn)檫f歸式歸并需要(1)與原始記錄相同大小的空間來(lái)存放歸并的結(jié)果以及(2)深度為logn的椗窃浚空間衔蹲，所以空間復(fù)雜度為O(n+logn)
非遞歸式歸并
演示
又比如我們待排序的數(shù)組是 {9, 1, 5, 8, 3, 7, 4, 6, 2}，那么非遞歸式的歸并排序?yàn)榱鞒虨椋?/p>
[9] [1] [5] [8] [3] [7] [4] [6] [2]
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
[1, 9] [5, 8] [3, 7] [4, 6] [2]
↓ ↓ ↓ ↓ ↓
[1, 5, 8, 9] [3, 4, 6, 7] [2]
↓ ↓ ↓
[1, 3, 4, 5, 6, 7, 8, 9] [2]
↓ ↓
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Java實(shí)現(xiàn)
// 非遞歸式歸并排序
class NonRecursiveMergeSorter extends MergeSorter {
@Override
public int[] sort(int[] arr) {
mergeSort(arr);
return arr;
}
private void mergeSort(int[] arr) {
int len = arr.length;
int result[] = new int[len];
int k = 1;
while (k < len) {
mergePass(arr, result, k); // arr歸并至result,此時(shí)間隔為k
k = 2 * k; // 子序列長(zhǎng)度加倍
mergePass(result, arr, k); // result歸并至arr,此時(shí)間隔翻倍
k = 2 * k; // 子序列長(zhǎng)度加倍
}
}
/**
* 將數(shù)組src中相鄰長(zhǎng)度為interval的子序列兩兩歸并到des數(shù)組中
*
* @param src
* 源數(shù)組
* @param des
* 目標(biāo)數(shù)組
* @param interval
* 兩兩合并的子序列長(zhǎng)度
*/
private void mergePass(int[] src, int[] des, int interval) {
int i = 0;
int len = src.length;
while (i + 2 * interval - 1 < len) {
// 兩兩合并
merge(src, des, i, i + interval - 1, i + 2 * interval - 1);
i = i + 2 * interval;
}
if (i + interval - 1 < len - 1) {
// i+interval-1小于len-1呈础，說(shuō)明最后還剩余兩個(gè)子序列舆驶，只不過(guò)最后的一個(gè)子序列長(zhǎng)度不夠interval
// 那么將剩下的兩個(gè)子序列進(jìn)行合并
merge(src, des, i, i + interval - 1, len - 1);
} else {
// 否則，最后只剩下單個(gè)子序列而钞，則直接將該子序列加入到des尾部
for (; i < len; i++) {
des[i] = src[i];
}
}
}
}
復(fù)雜度
時(shí)間復(fù)雜度：
同遞歸式歸并沙廉，最好情況 = 最壞情況 = 平均情況 = O(nlogn)
空間復(fù)雜度：
非遞歸式歸并不需要保存方法棧信息，所以空間復(fù)雜度為O(n)
所以非遞歸的遞歸算法性能要高于遞歸式歸并算法笨忌。
