概述

如果一個數(shù)組有n個數(shù)據(jù)，則可以把這個數(shù)組看作n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，就能得到[n/2]個長度為2或1的子序列，再不斷地兩兩歸并，直到得到一個長度為n的有序數(shù)組。
這種排序方法稱為2路歸并排序

遞歸，java實(shí)現(xiàn)

public class MergeSort {
    public static void main(String[] args) {
        int[] array = {98, 21, 62, 48, 33, 6, 55, 17};
        System.out.print("MergeSort\n");
        printArray(array);
        System.out.print("start:\n");
        mergeSort(array, 0, array.length - 1);
        System.out.print("end:\n");
    }

    static void mergeSort(int[] arr, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            mergeSort(arr, low, mid);
            mergeSort(arr, mid + 1, high);
            merge(arr, low, mid, high);
        }
    }

    static void merge(int[] arr, int low, int mid, int high) {
        //temp數(shù)組用于暫存合并的結(jié)果
        int[] temp = new int[high - low + 1];
        //左半邊的指針
        int i = low;
        //右半邊的指針
        int j = mid+1;
        //合并后數(shù)組的指針
        int k = 0;

        //將記錄由小到大地放進(jìn)temp數(shù)組
        for(; i <= mid && j <= high; k++)
        {
            if(arr[i] < arr[j])
                temp[k] = arr[i++];
            else
                temp[k] = arr[j++];
        }

        //接下來兩個while循環(huán)是為了將剩余的（比另一邊多出來的個數(shù)）放到temp數(shù)組中
        while(i <= mid)
            temp[k++] = arr[i++];

        while(j <= high)
            temp[k++] = arr[j++];

        //將temp數(shù)組中的元素寫入到待排數(shù)組中
        for(int l = 0; l < temp.length; l++)
            arr[low + l] = temp[l];

        printArray(arr);

    }

    static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.print("\n");
    }
}

排序效果

MergeSort
98 21 62 48 33 6 55 17 
start:
21 98 62 48 33 6 55 17 
21 98 48 62 33 6 55 17 
21 48 62 98 33 6 55 17 
21 48 62 98 6 33 55 17 
21 48 62 98 6 33 17 55 
21 48 62 98 6 17 33 55 
6 17 21 33 48 55 62 98 
end:

復(fù)雜度

時(shí)間復(fù)雜度: O(nlogn)
空間復(fù)雜度: O(n+nlogn)