基本思路
將一個數(shù)組排序聊记，可以先（遞歸地）將它分成兩半分別排序撒妈，然后將結(jié)果歸并起來。
最基本的算法——?dú)w并操作
歸并：一個集合前半部分有序排监，后半部分也有序狰右，現(xiàn)在通過歸并的手段讓整體有序
基本算法：依次從兩個集合中取數(shù)據(jù)，誰小誰放前面
private static void mergeArray1(Comparable[] a, int start, int middle, int end) {
Comparable[] temp = new Comparable[end - start + 1];
int i = start;
int j = middle + 1;
int k = 0;
while ((i <= middle) && (j <= end)) {
if (less(a[i], a[j])) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
while (i <= middle) {
temp[k++] = a[i++];
}
while (j <= end) {
temp[k++] = a[j++];
}
System.arraycopy(temp, 0, a, start, end - start + 1);
}
我們可以看到歸并操作舆床，需要創(chuàng)建一個臨時集合來存放有序數(shù)據(jù)棋蚌，最后再把數(shù)據(jù)copy回原集合。歸并操作在歸并排序中是需要遞歸調(diào)用的挨队，頻繁的new 集合不合理谷暮。
原地歸并的方案
我們希望能夠盡可能的原地歸并數(shù)據(jù)，當(dāng)然不可能完全實(shí)現(xiàn)盛垦。一個可行的方案是：排序前建一個和原數(shù)組大小相等的輔助數(shù)組湿弦，在每一次merge操作時，將對應(yīng)的數(shù)據(jù)先copy過來腾夯，然后將數(shù)據(jù)從輔助數(shù)組排序到輸入數(shù)組颊埃。
private static void mergeArray2(Comparable[] a, int start, int middle,
int end, Comparable[] temp) {
int i = start;
int j = middle + 1;
int k = start;
System.arraycopy(a, start, temp, start, end - start + 1);
while ((i <= middle) && (j <= end)) {
if (less(temp[i], temp[j])) {
a[k++] = temp[i++];
} else {
a[k++] = temp[j++];
}
}
while (i <= middle) {
a[k++] = temp[i++];
}
while (j <= end) {
a[k++] = temp[j++];
}
}
我們看到mergeArray2和mergeArray1最大的區(qū)別就是：
mergeArray1歸并動作在輔助數(shù)組中完成，輔助數(shù)組完成歸并后蝶俱，再arrayCopy回原數(shù)組班利。
而直接mergeArray2在原數(shù)組中歸并。也就是所謂的原地歸并榨呆。
自頂向下的歸并排序（遞歸）
上面我們已經(jīng)有了基本的歸并算法罗标，那么歸并排序也就很清晰了：
1.找到數(shù)組的middle
2.遞歸的對上半部分排序，遞歸的對下半部分排序
3.歸并操作
幾個注意的點(diǎn)：
- 當(dāng)遞歸到一定程度，數(shù)組元素已經(jīng)比較少的時候馒稍，可以使用插入或者選擇排序進(jìn)行排序
- 由于上下兩部分都是有序數(shù)組皿哨，當(dāng)恰好a[middle]<a[middle+1]時，就可以認(rèn)為已經(jīng)是有序的纽谒。
public static void merge_sort(Comparable[] a) {
Comparable[] temp = new Comparable[a.length];
mergesort(a, 0, a.length - 1, temp);
}
private static void mergesort(Comparable[] a, int start, int end,
Comparable[] temp) {
if (end - start + 1 < 15) { //小于15的數(shù)據(jù)，可以采用插入或者選擇排序
select_sort(a, start, end);
} else {
int middle = (start + end) / 2;
if (start < end) {
mergesort(a, start, middle, temp);
mergesort(a, middle + 1, end, temp);
if (!less(a[middle], a[middle + 1])) { //如果a[middle]< a[middle + 1],我們認(rèn)為已經(jīng)有序
mergearray(a, start, middle, end, temp);
}
}
}
}
自底向上的歸并排序（非遞歸如输，適合鏈表）
既然有遞歸的方案鼓黔，那反過來一定有非遞歸的方案。
方案：歸并微型數(shù)組不见，然后成對歸并得到的子數(shù)組澳化，直到將整個數(shù)組歸并到一起。
- mergeArray(0,0,1) mergeArray(2,2,3)—— mergeArray(0,1,3)
- mergeArray(0,1,3) mergeArray(4,5,7)—— mergeArray(0,3,7)
- mergeArray(0,3,7) mergeArray(8,11,15)
- 如此反復(fù)稳吮，直到合并為一個大小為N的數(shù)組
private static void mergeBU_sort(Comparable[] a) {
Comparable[] temp = new Comparable[a.length];
int N = a.length;
for (int sz = 1; sz < N; sz = sz + sz) { // sz為每次歸并的數(shù)組長度缎谷，從1開始，一直到N/2
for (int start = 0; start < N - sz; start += sz + sz) { // 對每一個數(shù)組進(jìn)行mergearray操作
int middle = start + sz - 1;
int end = start + sz - 1 + sz;
mergearray(a, start, middle,
Math.min(end, N - 1), temp);
}
}
}
