归并排序模板(Java)
《算法导论》学习记录
/** * 归并排序 * O(nlogn) * @param A 待排序的数组 * @param p 数组的左端点:1 * @param r 数组的右端点:A.length */ public static void MERGESORT(int[] A, int p, int r) { if(p < r) { int q = (p + r) / 2; // 1. 先分解待排序的数组,成两个子序列 MERGESORT(A, p, q); MERGESORT(A, q + 1, r); // 2.3. 解决排序并合并 MERGE_UP(A, p, q, r); } } public static void MERGE_UP(int[] A, int p, int q, int r) { // 分别取两个子序列的长度新建两个数组(此时两个子序列已经各自排好序) int lenleft = q - p + 1; int lenright = r - q; // 在数组的末尾设立一个极值(设置哨兵) int[] L = new int[lenleft + 1]; int[] R = new int[lenright + 1]; for(int i = 0; i < lenleft; i++) { L[i] = A[p - 1 + i]; } for(int j = 0; j < lenright; j++) { R[j] = A[q + j]; } L[lenleft] = Integer.MAX_VALUE; // 取极值 R[lenright] = Integer.MAX_VALUE; // 合并两个子序列(归并排序) int i = 0, j = 0; for(int k = p - 1; k < r; k++) { // 由于 Java 数组从 0 下标开始,所以要做一些处理 // 把 <= 换成 >= 即可变成降序归并,同时需要把 MAX_VALUE 改成 MIN_VALUE if(L[i] <= R[j]) { A[k] = L[i++]; } else { A[k] = R[j++]; } } // 此时 A[p..r] 已排好序 }