归并排序的代码实现(二路归并,java语言)
归并排序
算法实现思想:先递归划分子序列,再回溯归并
/** * className:Sort * * @author:zjl * @version:0.1 * @date:2020/8/817:17 * @since:jdk1.8 */public class Sort { //测试 public static void main(String[] args) { int[] A = {1, 3, 8, 4, 7, 5, 2, 6, 9}; mergeSort(A, 0, A.length - 1); for (int i = 0; i < A.length; i++) { System.out.print(A[i] + " "); } } /** * 二路归并排序 * @param R * @param low 数组要归并部分的起始索引值 * @param high 数组要归并部分的结束索引值 * @return */ public static int[] mergeSort(int[] R, int low, int high) { if (low < high) { int mid = (high + low) / 2; mergeSort(R, low, mid );//递归 (归并排序R的左半部分) mergeSort(R, mid+1, high);//递归 (归并排序R的右半部分) merge(R, low, mid, high); //把R中low —> mid 部分与mid+1 —> high部分归并为有序序列 } return R; } /** * 把R中low —> mid 部分与mid+1 —> high部分归并为有序序列 * 要归并前求R中low —> mid 部分与mid+1 —> high部分分别已经有序 * @param R * @param low * @param mid * @param high */ public static void merge(int[] R, int low, int mid, int high) { int j = mid+1; int n = low; int[] temp = new int[mid - low+1]; int i = 0; //复制数组R的 low —> mid 部分 for (int k = low, m = 0; k <= mid; k++, m++) { temp[m] = R[k]; } while (i < temp.length && j <= high) { if (temp[i] <= R[j]) { R[n] = temp[i]; n++; i++; } else { R[n] = R[j]; n++; j++; } } if (i < temp.length) { for (int m = i; m < temp.length; m++) { R[n] = temp[m]; n++; } } if (j <= high) { for (int m = j; m <= high; m++) { R[n] = R[m]; n++; } } }}
测试结果