Skip to content

Instantly share code, notes, and snippets.

@beiweiqiang
Created July 17, 2019 00:29
Show Gist options
  • Save beiweiqiang/a337dae7aa213435269d653beb86f6f0 to your computer and use it in GitHub Desktop.
Save beiweiqiang/a337dae7aa213435269d653beb86f6f0 to your computer and use it in GitHub Desktop.
java 实现归并排序, 自底向上
import java.util.Date;
public class MergeBU {
private static Comparable[] aux;
public static void sort(Comparable[] a) {
int n = a.length;
aux = new Comparable[n];
// 1 1 归并, 2 2 归并, 4 4 归并, 8 8 归并...
for (int sz = 1; sz < n; sz = sz + sz) {
// 每次归并都需要从 lo = 0 开始
for (int lo = 0; lo < n - sz; lo += sz + sz) {
merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, n - 1));
}
}
}
public static void merge(Comparable[] a, int lo, int mid, int hi) {
// lo, mid, hi 都是数组索引
int i = lo; int j = mid + 1;
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
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++];
}
}
}
// v 是否比 w 小 ? 如果返回 true: v < w
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
public static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++) {
if (less(a[i], a[i - 1])) {
return false;
}
}
return true;
}
public static long timeRandomInput(int len, int count) {
long total = 0;
Comparable[] a;
for (int i = 0; i < count; i++) {
a = Utils.generateRandomIntArray(len, 0, len - 1);
long start = (new Date()).getTime();
sort(a);
total += ((new Date()).getTime()) - start;
}
return total;
}
public static void main(String[] args) {
int len = 1000;
int min = 10;
int max = 1000;
Comparable[] a = Utils.generateRandomIntArray(len, min, max);
sort(a);
assert isSorted(a);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment