Created
July 17, 2019 00:12
-
-
Save beiweiqiang/18a3ee58c8b3dca1972095f77490beb9 to your computer and use it in GitHub Desktop.
java 实现归并排序, 自顶向下
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Date; | |
public class Merge { | |
private static Comparable[] aux; | |
public static void sort(Comparable[] a) { | |
aux = new Comparable[a.length]; | |
sort(a, 0, a.length - 1); | |
} | |
private 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); | |
// 如果 a[mid] 小于等于 a[mid + 1], 则可以认为数组已经是有序的了, 可以跳过 merge() | |
if (less(a[mid], a[mid + 1])) { | |
return; | |
} | |
merge(a, lo, mid, hi); | |
} | |
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[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; | |
// int minIndex = 0; | |
// int maxIndex = len - 1; | |
// int midIndex = minIndex + (maxIndex - minIndex) / 2; | |
Comparable[] a = Utils.generateRandomIntArray(len, min, max); | |
// show(a); | |
sort(a); | |
assert isSorted(a); | |
// aux = new Comparable[a.length]; | |
// merge(a, minIndex, midIndex, maxIndex); | |
// show(a); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment