在極客時間學(xué)習(xí)時，又遇到了歸并排序，這里給出Java的實現(xiàn)，附有注解，以備后面學(xué)習(xí)查看

private int[] sortArray(int[] waitDealArray) {
    if(waitDealArray == null) {
        return new int[0];
    }
    if(waitDealArray.length == 1) {
        return waitDealArray;
    }
    int middleIdx = waitDealArray.length / 2;
    // 將數(shù)組從中間分成左右兩個，分而治之
    int[] leftArray = Arrays.copyOfRange(waitDealArray, 0, middleIdx);
    int[] rightArray = Arrays.copyOfRange(waitDealArray, middleIdx, waitDealArray.length);
    // 遞歸調(diào)用處理子問題
    leftArray = sortArray(leftArray);
    rightArray = sortArray(rightArray);
    // 合并子問題處理的結(jié)果
    int[] mergedArray = mergeArray(leftArray, rightArray);
    return mergedArray;
}

private int[] mergeArray(int[] leftArray, int[] rightArray) {
    if(leftArray == null) {
        leftArray = new int[0];
    }
    if(rightArray == null) {
        rightArray = new int[0];
    }
    int[] mergedArray = new int[leftArray.length + rightArray.length];
    int mi = 0, li = 0, ri = 0;
    // 用來合并兩個有序數(shù)組內(nèi)的數(shù)字
    while(li < leftArray.length && ri < rightArray.length) {
        if(leftArray[li] <= rightArray[ri]) {
            mergedArray[mi] = leftArray[li];
            li++;
        } else {
            mergedArray[mi] = rightArray[ri];
            ri++;
        }
        mi++;
    }
    // 如果某個數(shù)組還有剩余數(shù)字，直接放入合并數(shù)組即可
    if(li < leftArray.length) {
        for(int i = li; i < leftArray.length; i++) {
            mergedArray[mi] = leftArray[li];
            mi++;
        }
    }
    if(ri < rightArray.length) {
        for(int i = ri; i < rightArray.length; i++) {
            mergedArray[mi] = rightArray[i];
            mi++;
        }
    }
    return mergedArray;
}

寫一個測試用例測試下:

/**
 * 測試歸并排序操作
 */
@Test
public void testUnionSort() {
    int[] waitDealArray = {234, 12, 45, 2, 908, 111, 309, 103, 205, 9};
    int[] sortedArray = sortArray(waitDealArray);
    System.out.println(Arrays.toString(sortedArray));
}

打印結(jié)果：

[2, 9, 12, 45, 103, 111, 205, 234, 309, 908]