import java.util.Arrays;
public class MergeSort { public static void mergeSort(int[] a, int start, int end) { if (start < end) { int mid = (start + end) / 2; mergeSort(a, start, mid); mergeSort(a, mid + 1, end);
merge(a, start, mid, end); } }
private static void merge(int[] a, int start, int mid, int end) { int[] temp = new int[a.length]; int i = start, j = mid + 1, k = start; while (i <= mid && j <= end) { if (a[i] < a[j]) { temp[k] = a[i]; k++; i++; } else { temp[k] = a[j]; k++; j++; } } if (i > mid) { while (j <= end) { temp[k] = a[j]; k++; j++; } } else { while (i <= mid) { temp[k] = a[i]; k++; i++; } } for (k = start; k <= end; k++) { a[k] = temp[k]; } }
/** * 非递归版本 * mergeSort sort the int array a * @param a * the array to be sorted **/ public static void mergeSort(int[] a) { int[] b = new int[a.length]; int s = 1; while (s < a.length) { mergePass(a, b, s); //合并到数组b s += s; mergePass(b, a, s); //合并到数组a s += s; } }
/** * mergePass用于合并排好序的相邻数组段,具体的合并算法由merge来实现 * @param x * the src * @param y * the des * @param s * the size of merge array **/ public static void mergePass(int[] x, int[] y, int s) { int i = 0; while (i < x.length - 2 * s) { //合并大小为s的相邻2段子数组 merge(x, y, i, i + s - 1, i + 2 * s - 1); i += 2 * s; } //剩下的元素少于2 * s if (i + s < x.length) {//剩下的元素小于 2 * s 但大于 s merge(x, y, i, i + s - 1, x.length - 1); } else { //剩下的元素小于 s ,复制到y for (int j = i; j < x.length; j++) { y[j] = x[j]; } } }
/** * 合并c[l:m]和c[m+1:r]到d[l:r] * * @param c * the src array * @param d * the des array * @param l * the start * @param m * the mid * @param r * the end * **/ public static void merge(int[] c, int[] d, int l, int m, int r) { int i = l; int j = m + 1; int k = l; while ((i <= m) && (j <= r)) { if (c[i] <= c[j]) { d[k++] = c[i++]; } else { d[k++] = c[j++]; } } if (i > m) { for (int q = j; q <= r; q++) { d[k++] = c[q]; } } else { for (int q = i; q <= m; q++) { d[k++] = c[q]; } } }
public static void main(String[] args) { int[] a = { 3, 4, 1, 5, 9, 3, 2, 8, 10 }; int[] b = { 3, 4, 1, 5, 9, 3, 2, 8, 10 }; mergeSort(a, 0, a.length - 1); mergeSort(b); System.out.println(Arrays.toString(a)); System.out.println(Arrays.toString(b)); } }
|