Skip to content

Instantly share code, notes, and snippets.

@dispensable
Last active July 14, 2016 11:11
Show Gist options
  • Save dispensable/d9739c26fb8bc61c944c126e8d7c6e64 to your computer and use it in GitHub Desktop.
Save dispensable/d9739c26fb8bc61c944c126e8d7c6e64 to your computer and use it in GitHub Desktop.
归并排序
/**原地归并排序
* Created by dispensable on 16/7/13.
*/
public class MergeSort {
private static Comparable[] aux;
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; 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[i], aux[j])) {
a[k] = aux[i++];
}
// 左边比右边大
else {
a[k] = aux[j++];
}
}
}
public static void sort(Comparable[] a) {
aux = new Comparable[a.length];
topDownSort(a, 0, a.length - 1);
}
private static void topDownSort(Comparable[]a, int lo, int hi) {
if (hi <= lo) return;
int mid = (lo + hi) / 2;
topDownSort(a, lo, mid);
topDownSort(a, mid + 1, hi);
merge(a, lo, mid, hi);
}
private static void downTopSort(Comparable[] a) {
int N = a.length;
aux = new Comparable[N];
for (int size = 1; size < N; size += size) {
for (int i = 0; i < N - size; i += (size + size)) {
merge(a, i, i + size - 1, Math.min(i + size + size - 1, N - 1));
}
}
}
private static boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
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])) {
System.out.println("Not sorted! " + a[i]);
return false;
}
}
return true;
}
public static void main(String[] args) {
System.out.print("\nTopDownMerge: ");
Integer[] b = {3, 2, 1, 6, 5, 0, 4};
show(b);
sort(b);
isSorted(b);
show(b);
}
}
@dispensable
Copy link
Author

TopDownMerge: 3216504
Not sorted! 4
0123645

@dispensable
Copy link
Author

复制到了aux数组就应该用aux[num]来比较,而不是用a

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment