> 文档中心 > 归并排序的代码实现(二路归并,java语言)

归并排序的代码实现(二路归并,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++;     } }    }}

测试结果
归并排序的代码实现(二路归并,java语言)