/** * 排序算法学习之合并排序 * @author Sking 实现方法: 将待排序数组中相邻元素两两配对作为子数组,排序各个子数组, 构成n/2组长度为2的排序好的子数组;然后将长度为2的子排序 子数组再两两配对,并排序,构成长度为4的已排序子数组。如此递归 直到整个数组是已排序为止。 最坏时间复杂度:O(n*log(n)) 平均时间复杂度:O(n*log(n)) 辅助空间:O(n) 稳定性:稳定 */ package 递归分治; public class MergeSort { @SuppressWarnings("rawtypes") /** * 对输入数组执行合并排序 * @param a 指定数组,索引有效位置从0开始 */ public void mergeSort(Comparable[] a) { Comparable[] b = new Comparable[a.length];// 辅助空间 int s = 1;// 初始子数组长度设置为1 while (s < a.length) { mergePass(a, b, s); s += s; mergePass(b, a, s); s += s; } } /** * 合并相邻的已排序子数组为更大的已排序子数组 * * @param x * 包含了已排序子数组的数组 * @param y * 包含更大的已排序子数组的数组 * @param s * 已排序子数组的长度 */ @SuppressWarnings("rawtypes") public static void mergePass(Comparable[] x, Comparable[] y, int s) { int i = 0; while (i <= x.length - 2 * s) {// 合并两相邻的长度为s的已排序子数组 merge(x, y, i, i + s - 1, i + 2 * s - 1); i = i + 2 * s; }// 当i>x.length-2*s的时候退出while循环 // 处理剩下的部分,可以是s长度的已排序数组+“零片” // 也可能只是“零片“,此时不需要合并。 if (i + s < x.length) { // 合并相邻的长度s的已排序子数组和长度小于s的“零片” merge(x, y, i, i + s - 1, x.length - 1); } else // 处理”零片“ for (int j = i; j < x.length; j++) y[j] = x[j]; } /** * 合并已排序子数组c[l...m]和c[m+1,r]到新数组中,新数组保持有序 * * @param c存放两个已排序数组的数组 * @param d * 新数组,用于存放合并后的数组 * @param l * 左边子数组的起始索引 * @param m * 左边子数组的结束索引 * @param r * 右边子数组的结束索引 */ @SuppressWarnings({ "unchecked", "rawtypes" }) static void merge(Comparable[] c, Comparable[] 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].compareTo(c[j]) <= 0) 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) { } }