合并排序
消去递归后的合并排序算法可描述：
public static void mergeSort(Comparable[] a) {
Comparable[] b = new Comparable[a.length];
int s = 1;
while (s < a.length) {
mergePass(a, b, s);
s += s;
mergePass(b, a, s);
s += s;
}
System.out.println(Arrays.toString(a));
}
其中，算法mergePass 用于合并排好序的相邻数组段，具体的合并算法由merge来实现。
public static void mergePass(Comparable[] x, Comparable[] y, int s) {
int i = 0;
while (i <= x.length - 2 * s) {
merge(x, y, i, i + s - 1, i + 2 * s - 1);
i = i + 2 * s;
}
if (i + s < x.length) {
merge(x, y, i, i + s - 1, x.length - 1);
} else {
for (int j = i; j < x.length; j++) {
y[j] = x[j];
}
}
}
public static void merge(Comparable[] a, Comparable[] b, int m, int n, int r) {
int i = m, j = n + 1, k = m;
while ((i <= n) && (j <= r)) {
while ((i <= n) && (j <= r)) {
if (a[i].compareTo(a[j]) <= 0) {
b[k++] = a[i++];
} else {
b[k++] = a[j++];
}
}
if (i > n) {
for (int q = j; q <= r; q++) {
b[k++] = a[q];
}
} else {
for (int q = i; q <= n; q++) {
b[k++] = a[q];
}
}
}
}
整体代码
package 练习;
import java.util.Arrays;
public class qSort {
public static void mergeSort(Comparable[] a) {
Comparable[] b = new Comparable[a.length];
int s = 1;
while (s < a.length) {
mergePass(a, b, s);
s += s;
mergePass(b, a, s);
s += s;
}
System.out.println(Arrays.toString(a));
}
public static void mergePass(Comparable[] x, Comparable[] y, int s) {
int i = 0;
while (i <= x.length - 2 * s) {
merge(x, y, i, i + s - 1, i + 2 * s - 1);
i = i + 2 * s;
}
if (i + s < x.length) {
merge(x, y, i, i + s - 1, x.length - 1);
} else {
for (int j = i; j < x.length; j++) {
y[j] = x[j];
}
}
}
public static void merge(Comparable[] a, Comparable[] b, int m, int n, int r) {
int i = m, j = n + 1, k = m;
while ((i <= n) && (j <= r)) {
while ((i <= n) && (j <= r)) {
if (a[i].compareTo(a[j]) <= 0) {
b[k++] = a[i++];
} else {
b[k++] = a[j++];
}
}
if (i > n) {
for (int q = j; q <= r; q++) {
b[k++] = a[q];
}
} else {
for (int q = i; q <= n; q++) {
b[k++] = a[q];
}
}
}
}
public static void main(String[] args) {
Comparable[] a = {4, 8, 3, 7, 1, 5, 2, 6};
System.out.print(Arrays.toString(a));
System.out.println();
mergeSort(a);
}
}
输出结果如下：
