public static void sort(Comparable[] a) {
Comparable[] aux = new Comparable[a.length];
sort(a, aux, 0, a.length - 1);
assert isSorted(a);
}
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 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++];
else if (j > hi)
a[k] = aux[i++];
else if (less(aux[j], aux[i]))
a[k] = aux[j++];
else
a[k] = aux[i++];
}
assert isSorted(a, lo, hi);
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
private static boolean isSorted(Comparable[] a) {
return isSorted(a, 0, a.length - 1);
}
private 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;
}
上述時間復(fù)雜度為O(nlgn)，空間復(fù)雜度為O(n),適用于排序大列表因悲，基于分治法。
下列圖片來展示長度16數(shù)組歸并過程
歸并結(jié)果軌跡
調(diào)用軌跡
歸并排序有以下幾點優(yōu)化方法：
- 和快速排序一樣，對于小數(shù)組可以使用插入排序或者選擇排序窥岩，避免遞歸調(diào)用。
- 在merge()調(diào)用之前宰缤，可以判斷一下a[mid]是否小于等于a[mid+1]颂翼。如果是的話那么就不用歸并了，數(shù)組已經(jīng)是有序的慨灭。原因很簡單朦乏，既然兩個子數(shù)組已經(jīng)有序了，那么a[mid]是第一個子數(shù)組的最大值氧骤，a[mid+1]是第二個子數(shù)組的最小值呻疹。當(dāng)a[mid]<=a[mid+1]時，數(shù)組整體有序筹陵。
- 為了節(jié)省將元素復(fù)制到輔助數(shù)組作用的時間刽锤，可以在遞歸調(diào)用的每個層次交換原始數(shù)組與輔助數(shù)組的角色镊尺。
- 在merge()方法中的歸并過程需要判斷i和j是否已經(jīng)越界，即某半邊已經(jīng)用盡并思÷可以用另一種方式，去掉檢測是否某半邊已經(jīng)用盡的代碼宋彼。具體步驟是將數(shù)組a[]的后半部分以降序的方式復(fù)制到aux[]弄砍，然后從兩端歸并。對于數(shù)組{1,2,3}和{2,3,5},第一個子數(shù)組照常復(fù)制输涕，第二個則從后往前復(fù)制音婶，最終aux[]中的元素為{1,2,3,5,3,2}。這種方法的缺點是使得歸并排序變?yōu)椴环€(wěn)定排序莱坎。代碼實現(xiàn)如下：
void merges(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
for (int k = lo; k <= mid; k++) {
aux[k] = a[k];
}
for(int k = mid+1; k <= hi; k++) {
aux[k] = a[hi-j+mid+1];
}
int i = lo, j = hi;
for (int k = lo; k <= hi; k++) {
if (less(aux[j], aux[i])) {
a[k] = aux[j--];
}
else {
a[k] = aux[i++];
}
}
}
下面代碼將上述前三種優(yōu)化結(jié)合在一起
public void sort(Comparable[] a) {
Comparable[] aux = a.clone();
//將aux放在第一位
sort(aux,a,0,a.length-1);
assert isSorted(a);
}
private void sort(Comparable[] src, Comparable[] dst, int lo, int hi) {
if (hi <= lo + CUTOFF) {
insertionSort(dst, lo, hi);
return;
}
int mid = (lo + hi)/2;
//對調(diào)
sort(dst, src, lo, mid);
sort(dst, src, mid+1, hi);
// if (less(src[mid], src[mid+1])) {
// for (int i = lo; i <= hi; i++) dst[i] = src[i];
// return;
// }
//更快
if (less(src[mid], src[mid+1])) {
System.arraycopy(src, lo, dst, lo, hi-lo+1);
return;
}
//對調(diào)
merge(src, dst, lo, mid, hi);
}
private void merge(Comparable[] src, Comparable[] dst, int lo, int mid, int hi) {
assert isSorted(src, lo, mid);
assert isSorted(src, mid+1, hi);
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) dst[k] = src[j++];
else if (j > hi) dst[k] = src[i++];
else if (less(src[i], src[j])) dst[k] = src[i++];
else dst[k] = src[j++];
}
assert isSorted(dst, lo, hi);
}
private void insertionSort(Comparable[] a, int lo, int hi) {
for (int i = lo; i <= hi; i++) {
for (int j = i; j>lo && less(a[j], a[j-1]); j--) {
exch(a, j, j-1);
}
}
}
還有一種非遞歸版本：
public void sort(Comparable[] a) {
int n = a.length;
Comparable[] aux = new Comparable[n];
for (int len = 1; len < n; len *= 2) {
//自底向上的歸并排序桃熄，先前一個與后一個排，再前兩個與后兩個型奥，再前四個與后四個...
//要考慮到末尾元素不夠的情況
for (int lo = 0; lo < n - len; lo += len * 2) {
int hi = Math.min(lo + len * 2 - 1, n - 1);
int mid = lo + len - 1;
merge(a, aux, lo, mid, hi);
}
}
}
public void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int 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++];
else if (j > hi)
a[k] = aux[i++];
else if (less(aux[j], aux[i]))
a[k] = aux[j++];
else
a[k] = aux[i++];
}
}
1.jpg
