递归---归并排序

2019-02-17 01:50:34来源：博客园阅读 ()

归并算法的中心是归并两个已经有序的数组。归并两个有序数组A、B，生成一个包含A、B的有序数组C

以下是归并算法代码

import org.junit.Test;

import java.util.Arrays;

public class MergeSort {


    @Test
    public void doTest() {
        int[] arrA = {2,5,14,44};
        int[] arrB = {4,9,10,11,33,67,89,99};
        int[] arrC = merge(arrA,arrB);
        System.out.println("数组A" + Arrays.toString(arrA));
        System.out.println("数组B" + Arrays.toString(arrB));
        System.out.println("数组C" + Arrays.toString(arrC));

    }

    public int[] merge(int[] arrA,int[] arrB){
        int sizeA = arrA.length;
        int sizeB = arrB.length;
        int[] arrC = new int[sizeA + sizeB];

        int aDex = 0,bDex = 0,cDex = 0;
        while (aDex < sizeA && bDex <sizeB){ //数组A和B都未比较完时执行
            if(arrA[aDex] > arrB[bDex]){
                arrC[cDex++] = arrB[bDex++];
            }else {
                arrC[cDex++] = arrA[aDex++];
            }
        }

        while (aDex <sizeA){
            arrC[cDex++] = arrA[aDex++];
        }

        while (bDex <sizeB){
            arrC[cDex++] = arrB[bDex++];
        }
        return arrC;
    }
}

归并排序的思想是将一个数组拆分成2个数组，排序每一半，然后再合并成一个有序数组，

递归归并算法是将一个数组，无限拆分成只有一个数据项的数组，然后再归并成一个有序数组

先写一个归并排序工具类

import org.junit.Test;

import java.util.Arrays;

public class DArray {
    private static int[] theArray; 

    public static int[] mergeSort(int[] arr){
        theArray = arr;
        int[] workSpace = new int[arr.length];
        recMergeSort(workSpace,0,arr.length-1);
        return theArray;
    }

    private static void recMergeSort(int[] workSpace,int lower,int upper){
        if(lower == upper){
            return;
        }else {
            int mid = (lower + upper)/2;
            recMergeSort(workSpace,lower,mid);
            recMergeSort(workSpace,mid + 1,upper);
            merge(workSpace,lower,mid+1,upper);
        }
    }

    private static void merge(int[] workSpace, int lower, int high, int upper) {
        int j = 0;
        int lowerBound = lower;
        int mid = high -1;
        int n = upper - lower + 1;
        while (lower <= mid && high <= upper){
           if(theArray[lower] < theArray[high]){
               workSpace[j++] = theArray[lower++];
           }else {
               workSpace[j++] = theArray[high++];
           }
        }
        while (lower <= mid){
            workSpace[j++] = theArray[lower++];
        }
        while (high <= upper){
            workSpace[j++] = theArray[high++];
        }
        for(j = 0; j < n; j++){
            theArray[lowerBound + j] = workSpace[j];
        }
    }
}

写一个测试方法测试代码

    @Test
    public void mergeSort(){
        int[] arr = new int[10];
        Random random = new Random();
        for(int i = 0;i < arr.length;i++){
            arr[i] = random.nextInt(100);
        }
        System.out.println("未排序前数组：" + Arrays.toString(arr));

        arr = DArray.mergeSort(arr);

        System.out.println("排序后数组：" + Arrays.toString(arr));

    }