歸并排序介紹

平均時(shí)間復(fù)雜度： O(NLogN)
最好情況時(shí)間復(fù)雜度： O(NLogN)
最差情況時(shí)間復(fù)雜度： O(NLogN)
所需要額外空間： 遞歸：O(N + LogN)， 非遞歸：O（N）
穩(wěn)定性： 穩(wěn)定

歸并排序基于分治（快排也是），利用歸并來(lái)實(shí)現(xiàn)排序，其基本思想是：

如果一個(gè)數(shù)組有n個(gè)數(shù)據(jù)，則可以把這個(gè)數(shù)組看作n個(gè)有序的子序列，每個(gè)子序列的長(zhǎng)度為1，然后兩兩歸并，就能得到[n/2]個(gè)長(zhǎng)度為2（或者1，落單的)的字序列，再不斷地兩兩歸并，直到得到一個(gè)長(zhǎng)度為n的有序數(shù)組。

這里選擇Merge就能比較直觀(guān)地看到歸并排序的過(guò)程。

使用遞歸的歸并排序

理解這個(gè)基本思想后，就不難寫(xiě)出歸并排序的代碼，只要遞歸地進(jìn)行歸并就行了.
其中歸并函數(shù)<code>merge</code>也很好理解，就是合并兩個(gè)有序數(shù)組為一個(gè)有序數(shù)組即可。

package com.yenghye.sort;

public class Sort {

    public static void MergeSort(int[] arr, int low, int high)
    {
        //使用遞歸的方式進(jìn)行歸并排序，所需要的空間復(fù)雜度是O（N+logN）
        int mid = (low + high)/2;
        if(low < high)
        {
            //遞歸地對(duì)左右兩邊進(jìn)行排序
            MergeSort(arr, low, mid);
            MergeSort(arr, mid+1, high);
            //合并
            merge(arr, low, mid, high);
        }
    }
    
    //merge函數(shù)實(shí)際上是將兩個(gè)有序數(shù)組合并成一個(gè)有序數(shù)組
    //因?yàn)閿?shù)組有序，合并很簡(jiǎn)單，只要維護(hù)幾個(gè)指針就可以了
    private 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++];
        }
        
        //接下來(lái)兩個(gè)while循環(huán)是為了將剩余的（比另一邊多出來(lái)的個(gè)數(shù)）放到temp數(shù)組中
        while(i <= mid)
            temp[k++] = arr[i++];
        
        while(j <= high)
            temp[k++] = arr[j++];
        
        //將temp數(shù)組中的元素寫(xiě)入到待排數(shù)組中
        for(int l = 0; l < temp.length; l++)
            arr[low + l] = temp[l];
    }
    
}

歸并排序的優(yōu)化（非遞歸歸并排序）

但是,使用遞歸的歸并排序需要深度為L(zhǎng)ogN的?？臻g，雖然代碼很簡(jiǎn)單易懂，但是會(huì)造成時(shí)間和空間上的性能損耗，為了優(yōu)化歸并排序，我們可以使用迭代代替遞歸。

package com.yenghye.sort;

public class Sort {

    public static void MergeSort2(int[] arr)
    {
        //使用非遞歸的方式來(lái)實(shí)現(xiàn)歸并排序
        int len = arr.length;
        int k = 1;
        
        while(k < len)
        {
            MergePass(arr, k, len);
            k *= 2;         
        }
    }
    
    //MergePass方法負(fù)責(zé)將數(shù)組中的相鄰的有k個(gè)元素的字序列進(jìn)行歸并
    private static void MergePass(int[] arr, int k, int n)
    {
        int i = 0;
        int j;
        
        //從前往后,將2個(gè)長(zhǎng)度為k的子序列合并為1個(gè)
        while(i < n - 2*k + 1)
        {
            merge(arr, i, i + k-1, i + 2*k - 1);
            i += 2*k;
        }
        
        //這段代碼保證了，將那些“落單的”長(zhǎng)度不足兩兩merge的部分和前面merge起來(lái)。
        if(i < n - k )
        {
            merge(arr, i, i+k-1, n-1);
        }
        
    }
    
    //merge函數(shù)實(shí)際上是將兩個(gè)有序數(shù)組合并成一個(gè)有序數(shù)組
    //因?yàn)閿?shù)組有序，合并很簡(jiǎn)單，只要維護(hù)幾個(gè)指針就可以了
    private 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++];
        }
        
        //接下來(lái)兩個(gè)while循環(huán)是為了將剩余的（比另一邊多出來(lái)的個(gè)數(shù)）放到temp數(shù)組中
        while(i <= mid)
            temp[k++] = arr[i++];
        
        while(j <= high)
            temp[k++] = arr[j++];
        
        //將temp數(shù)組中的元素寫(xiě)入到待排數(shù)組中
        for(int l = 0; l < temp.length; l++)
            arr[low + l] = temp[l];
    }
}

非遞歸而是迭代的歸并排序很直觀(guān)，就是從前往后從最小的序列開(kāi)始?xì)w并，直到完成即可。
但是這里邊界條件不太好想，要注意不要出錯(cuò)。