下面是代码 我的问题是 Merge方法里面的那四种判断是根据什么来的?j>hi是怎么回事,
public class Merge {
private static Comparable[] b;
public static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
public static void merge(Comparable[] a, int lo, int mid, int hi) {
int i = lo;
int j = mid + 1;
for (int k = lo; k < hi + 1; k++) {
b[k] = a[k];
}
for (int k = lo; k < hi + 1; k++) {
if (i > mid) {
a[k] = b[j++];
} else if (j > hi) {
a[k] = b[i++];
} else if (less(b[i], b[j])) {
a[k] = b[i++];
} else {
a[k] = b[j++];
}
}
}
/**
* 自顶向下和自底向上
*
* @param a
*/
public static void sort(Comparable[] a) {
b = new Comparable[a.length];
// 自顶向下
sort(a, 0, a.length - 1);
//自底向上
// for (int i = 1; i < a.length; i++) {
// for (int lo = 0; lo < a.length - i; lo += i + i) {
// merge(a, lo, lo + i - 1, Math.min(lo + i + i - 1, a.length - 1));
// }
// }
}
public static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) {
return;
}
int mid = lo + (hi - lo) / 2;
sort(a, lo, mid);
sort(a, mid + 1, hi);
merge(a, lo, mid, hi);
}
public static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
Integer[] a = new Integer[10];
for (int i = 0; i < 10; i++) {
a[i] = (int) (Math.random() * 10 + 1);
}
show(a);
sort(a);
show(a);
}
}
int lo, int mid, int hi
分别是待归并的两部分数组的起始位置,第一个是lo~mid,第二个是mid+1~hi
int i = lo;
int j = mid + 1;
开始的时候,i和j分别指向两部分数组的开始位置
for (int k = lo; k < hi + 1; k++) {
b[k] = a[k];
}
首先复制一份拷贝到b里面,而原来的a数组的相应位置则保存排序后的结果
for (int k = lo; k < hi + 1; k++) {
if (i > mid) { //i > mid说明第一个数组中的数据都已经插入到a里面了,而第二个数组是有序的,所以照着复制就可以
a[k] = b[j++];
} else if (j > hi) { //j>h说明第二个数组已经都插入进去了,而第一个数组是有序的,所以照着复制
a[k] = b[i++];
} else if (less(b[i], b[j])) { //第一个数组的当前元素比第二个小,那么先插入第一个数组的(插入后i往后移动一个),第二个不动。
a[k] = b[i++];
} else { //第一个数组比第二个大,那么先插入第二个的,第一个不动
a[k] = b[j++];
}
}