1 思路
假設(shè)有這樣一個數(shù)組：
數(shù)組
歸并排序的思路是，將這個數(shù)組先不斷的拆分為二，直至只有一個子元素。然后不斷的向上合并已排好序的子數(shù)組。
歸并排序過程
因此，大概的流程是這樣：
- 將一個大的數(shù)組分成兩部分子數(shù)組
- 分別對兩個子數(shù)組進(jìn)行排序
- 將兩個已排好序的子數(shù)組進(jìn)行合并
- 大的數(shù)組也已經(jīng)排好序了
因此，假設(shè)有一個函數(shù)，實(shí)現(xiàn)了上面的功能：
void sort(int[] aar, int l, int r) {
// 1.判斷待排序數(shù)組空間是否合法
if (l >= r)
return;
int mid = l + (r - l) / 2;
// 2.對左邊部分子數(shù)組進(jìn)行排序
sort(aar, l, mid);
// 3.對右邊數(shù)組進(jìn)行排序
sort(aar, mid+1, r);
// 4.合并兩部分?jǐn)?shù)組
merge(aar, l, mid, r);
}
由以上分析可知，歸并排序算法的核心在于實(shí)現(xiàn)merge函數(shù)，這也是該算法稱為歸并的原因。
2 實(shí)現(xiàn)
2.1 merge的實(shí)現(xiàn)
這里先實(shí)現(xiàn)merge。本質(zhì)上，merge就是將兩個已排好序的數(shù)組合并為一個排序數(shù)組，在這里只不過是將兩個已排好序的子數(shù)組合并為一個更大的排序子數(shù)組。
使用k來遍歷待排序的更大的子數(shù)組，用來放置合適的值。由于會發(fā)生值變換，因此需要先把數(shù)組中的元素拷貝一份。
使用i來遍歷左半部分的已排序數(shù)組，使用j來遍歷右半部分的已排序的數(shù)組。不斷的將兩部分i和j所指向的更小的元素拷貝到索引為k中。
代碼如下：
// 數(shù)組data的區(qū)間[l .. mid][mid+1 .. r]分別是有序的，對這兩個區(qū)間的元素進(jìn)行合并排序
private static <E extends Comparable<E>> void merge(E[] data, int l, int mid, int r) {
E[] temp = Arrays.copyOfRange(data, l, r + 1);
int i = l;
int j = mid + 1;
// k輪詢原數(shù)組待操作區(qū)域的索引，用于放入新元素
for (int k = l; k <= r; k++) {
if (j > r) {
data[k] = temp[i - l];
i++;
} else if (i > mid) {
data[k] = temp[j - l];
j++;
} else if (temp[i - l].compareTo(temp[j - l]) < 0) {
data[k] = temp[i - l];
i++;
} else {
data[k] = temp[j - l];
j++;
}
}
}
2.2 遞歸的實(shí)現(xiàn)
根據(jù)開始的偽代碼，實(shí)現(xiàn)對應(yīng)的Java代碼
public static <E extends Comparable<E>> void sort(E[] data) {
if (data == null || data.length <= 1) {
return;
}
sort(data, 0, data.length - 1);
}
// 對數(shù)組data的區(qū)間[l .. r]進(jìn)行排序
private static <E extends Comparable<E>> void sort(E[] data, int l, int r) {
// 最簡單的問題
if (l >= r) {
return;
}
// 先求解更小的問題
int mid = l + (r - l) / 2;
sort(data, l, mid);
sort(data, mid + 1, r);
// 根據(jù)最小問題的解解決當(dāng)前問題
merge(data, l, mid, r);
}
3算法復(fù)雜度分析
復(fù)雜度分析
由以上圖示可知，對于歸并算法的每一層，歸并所需要的操作的和都為8，推而廣之為n，因此每一層的算法復(fù)雜度為O(n)。
接下來在看層數(shù)，由于每次會一分為二，這可以看成是一個樹結(jié)構(gòu)，它的層數(shù)的量級為logn。
因此歸并排序算法的復(fù)雜度為O(nlogn)
4 優(yōu)化
4.1 判斷是否需要merge
如果兩部分已排序子數(shù)組，后半部分的最小索引的元素比前半部分最大索引的元素要大，此時，不需要重新排序：
// 對數(shù)組data的區(qū)間[l .. r]進(jìn)行排序
private static <E extends Comparable<E>> void sort2(E[] data, int l, int r) {
// 最簡單的問題
if (l >= r) {
return;
}
// 先求解更小的問題
int mid = l + (r - l) / 2;
sort2(data, l, mid);
sort2(data, mid + 1, r);
// 根據(jù)最小問題的解解決當(dāng)前問題
if (data[mid].compareTo(data[mid + 1]) > 0) {
merge(data, l, mid, r);
}
}
針對這個優(yōu)化，做一個100,000規(guī)模數(shù)據(jù)的排序比較結(jié)果如下：
MergeSort: n = 100000, costTime: 0.060000S // 未優(yōu)化
MergeSort2: n = 100000, costTime: 0.022000S // 已優(yōu)化
可以看到，優(yōu)化后的算法，在這個數(shù)據(jù)規(guī)模和我的電腦上，時間快了三倍。
另一方面，加入數(shù)組本來就是一個有序的，那么，將不會進(jìn)入到merge過程，整個算法的復(fù)雜度將會退化到O(n)級別。
4.2 使用插入排序排序較小子數(shù)組
歸并排序的merge算法相對來說操作步驟較多，當(dāng)數(shù)據(jù)規(guī)模較小時，更有可能有序，插入排序算法的性能可能會更好，因此，我們假設(shè)當(dāng)子數(shù)組數(shù)據(jù)量沒超過16時，使用插入排序。
首先，重新定義一個插入排序方法，允許排序一個數(shù)組的子數(shù)組區(qū)間：
// 對數(shù)組data的區(qū)間[l, r]進(jìn)行排序
public static <E extends Comparable<E>> void sort(E[] data, int l, int r) {
// 第一重循環(huán)，維持循環(huán)不變量data[l ... i)中的元素都是已排好序的
for (int i = l; i <= r; i++) {
// 第二重循環(huán)，將data[i]中的元素插入到已排好序的正確位置，不是合適的位置的元素，都往后挪一個索引
E t = data[i]; // 待插入元素
int j; // 待插入位置
for (j = i; j - 1 >= l && t.compareTo(data[j - 1]) < 0; j--) { // 該重循環(huán)的工作是尋找待插入的正確位置j
data[j] = data[j - 1];
}
data[j] = t;
}
}
然后，再改進(jìn)sort方法
// 對數(shù)組data的區(qū)間[l .. r]進(jìn)行排序
private static <E extends Comparable<E>> void sort2(E[] data, int l, int r) {
// 最簡單的問題
if (r - l <= 15) {
InsertionSort.sort(data, l, r);
return;
}
// 先求解更小的問題
int mid = l + (r - l) / 2;
sort2(data, l, mid);
sort2(data, mid + 1, r);
// 根據(jù)最小問題的解解決當(dāng)前問題
if (data[mid].compareTo(data[mid + 1]) > 0) {
merge(data, l, mid, r);
}
}
和只是進(jìn)行merge判斷優(yōu)化對比，在我的機(jī)子上針對100,000的數(shù)據(jù)，快了3倍多。
MergeSort: n = 100000, costTime: 0.073000S // merge判斷優(yōu)化
MergeSort2: n = 100000, costTime: 0.029000S // 進(jìn)一步插入排序優(yōu)化
4.3 一次性分配臨時數(shù)組
在上面的實(shí)現(xiàn)中，每一次merge都會創(chuàng)建一個新的臨時數(shù)組，這是非常耗性能的。我們可以一開始就定義一個的數(shù)組：
public static <E extends Comparable<E>> void sort2(E[] data) {
if (data == null || data.length <= 1) {
return;
}
E[] temp = (E[]) new Comparable[data.length];
sort2(data, 0, data.length - 1, temp);
}
// 對數(shù)組data的區(qū)間[l .. r]進(jìn)行排序
private static <E extends Comparable<E>> void sort2(E[] data, int l, int r, E[] temp) {
// 最簡單的問題
if (r - l <= 15) {
InsertionSort.sort(data, l, r);
return;
}
// 先求解更小的問題
int mid = l + (r - l) / 2;
sort2(data, l, mid, temp);
sort2(data, mid + 1, r, temp);
// 根據(jù)最小問題的解解決當(dāng)前問題
if (data[mid].compareTo(data[mid + 1]) > 0) {
merge2(data, l, mid, r, temp);
}
}
// 數(shù)組data的區(qū)間[l .. mid][mid+1 .. r]分別是有序的，對這兩個區(qū)間的元素進(jìn)行合并排序
private static <E extends Comparable<E>> void merge2(E[] data, int l, int mid, int r, E[] temp) {
System.arraycopy(data, l, temp, l, r - l + 1);
int i = l;
int j = mid + 1;
// k輪詢愿數(shù)組待操作區(qū)域的索引，用于放入新元素
for (int k = l; k <= r; k++) {
if (j > r) {
data[k] = temp[i++];
} else if (i > mid) {
data[k] = temp[j++];
} else if (temp[i].compareTo(temp[j]) < 0) {
data[k] = temp[i++];
} else {
data[k] = temp[j++];
}
}
}
在我的機(jī)子上，針對這樣的優(yōu)化的性能比較如下，可以看到，也是快了點(diǎn)：
MergeSort: n = 100000, costTime: 0.042000S // 已進(jìn)行了前兩步優(yōu)化
MergeSort2: n = 100000, costTime: 0.037000S // 增加統(tǒng)一數(shù)組分配優(yōu)化
自底向上歸并排序算法
上面實(shí)現(xiàn)的歸并排序算法，是將一個數(shù)組不斷拆分成兩個更小的數(shù)組，這樣一種思路是一種自頂向下的。另一種相反的思路是自底向上的。
例如對于一開始的八個元素，先對每兩個元素進(jìn)行合并：
每兩個元素進(jìn)行合并
然后在進(jìn)行每四個元素進(jìn)行合并：
每四個元素進(jìn)行合并
然后就是接下來，對所有8個元素進(jìn)行合并。
實(shí)現(xiàn)代碼如下，需要注意的是，當(dāng)數(shù)組長度不為2的n次方的時候，對于merge的右邊界值，需要和數(shù)組的邊界做比較：
public static <E extends Comparable<E>> void sort(E[] data) {
if (data == null || data.length <= 1) {
return;
}
E[] temp = (E[]) new Comparable[data.length];
int n = data.length;
// 遍歷合并的區(qū)間的長度
for (int sz = 1; sz < n; sz += sz) {
// 合并[i, i + sz -1]和[i + sz, Math.min(i + sz + sz - 1, n -1)]
for (int i = 0; i + sz < n; i += sz + sz) {
if (data[i + sz - 1].compareTo(data[i + sz]) > 0) {
merge(data, i, i + sz - 1, Math.min(n - 1, i + sz + sz - 1), temp);
}
}
}
}
