歸并排序

歸并排序的時(shí)間復(fù)雜度是O(n*log2n)就斤，是穩(wěn)定的

歸并排序的思想是分治法（Divide and Conquer）

首先思考一個(gè)問(wèn)題舷蟀，已經(jīng)排序的兩個(gè)數(shù)組如何融合為一個(gè)有序數(shù)組
數(shù)組a靡努，數(shù)組b撑蒜，b中的第一個(gè)與a中的第一個(gè)比較，小的那個(gè)放到臨時(shí)數(shù)組c中，一旦數(shù)組a或者b已經(jīng)遍歷完了粱檀，那么另外一個(gè)剩下的數(shù)組全部放到臨時(shí)數(shù)組即可

1.融合兩個(gè)已經(jīng)排序的數(shù)組片段

融合兩個(gè)已經(jīng)排序的數(shù)組段代碼如下：

/**
*a為排序數(shù)組，left為已排序左片段的下標(biāo)漫玄，mid為已排序左片段的最后一個(gè)下標(biāo)
*茄蚯，right為已排序的右片段的最后一個(gè)下標(biāo)，tem為臨時(shí)數(shù)組
*
**/
private static void mergeArray(int[] a ,int left,int mid,int right,int[] tem){
        //i為待會(huì)要進(jìn)行比較的左數(shù)組的游標(biāo)，j為右數(shù)組的游標(biāo)第队，k為臨時(shí)數(shù)組的游標(biāo)
        int i = left;
        int j = mid + 1;
        int k = left;
        
        //一旦某個(gè)數(shù)組片段已經(jīng)遍歷完了哮塞，退出循環(huán)
        while(i <= mid && j <= right){
            if(a[i] < a[j]){
                tem[k] = a[i];
                i++;
                k++;
            }else{
                tem[k] = a[j];
                j++;
                k++;
            }
        }
        
        //把那個(gè)未遍歷完的數(shù)組片段全部加到臨時(shí)數(shù)組即可
        while(i <= mid){
            tem[k] = a[i];
            i++;
            k++;
        }
        
        //與上一個(gè)while循環(huán)只會(huì)執(zhí)行其一，因?yàn)橹豢赡艹霈F(xiàn)一個(gè)片段有剩余
        while(j <= right){
            tem[k] = a[j];
            j++;
            k++;
        }
        
        //把臨時(shí)數(shù)組放回到原數(shù)組
        for(;left <= right;left++){
            a[left] = tem[left];
        }
    }

2.遞歸劃分出已排序的兩個(gè)數(shù)組片段

如何遞歸劃分出已排序的兩個(gè)數(shù)組片段凳谦？
如果那個(gè)數(shù)組片段只有一個(gè)元素忆畅，就可以看成它是有序的，以下代碼遞歸出這個(gè)片段：

    private static void mergeSortMethod(int [] array,int start ,int end ,int[] tem){
        //數(shù)組元素大于1的時(shí)候才進(jìn)行遞歸分割尸执。等于1就直接有序了
        if(start < end){
            //將一個(gè)數(shù)組分為兩段家凯，mid為左邊的最后一個(gè)下標(biāo)
            int mid = (start + end) / 2;
            //對(duì)左邊再進(jìn)行分割
            mergeSortMethod(array, start, mid, tem);
            //對(duì)右邊再進(jìn)行分割
            mergeSortMethod(array, mid + 1, end, tem);
            //歸并兩個(gè)已排序數(shù)組
            mergeArray(array, start, mid, end, tem);
        }
    

當(dāng)片段長(zhǎng)度為1的數(shù)組進(jìn)入上述方法時(shí)候，遞歸停止如失，然后進(jìn)行第一次的方法調(diào)用

mergeArray(array, start, mid, end, tem);

然后繼續(xù)上一層的遞歸出棧绊诲。最后完成整個(gè)調(diào)用。

3.調(diào)用mergeArray()方法：

public static void mergeSort(int[] array){
                //這場(chǎng)的臨時(shí)數(shù)組用的是同一個(gè)褪贵，導(dǎo)致空間復(fù)雜度是O(n)
        mergeSortMethod(array, 0, array.length - 1, new int[array.length]);
    }

4.完整代碼：

public class MergeSortSenninha {
    public static void main(String[] arg){
        int [] left = {1,2,5,7,889,3,4,6,7};
        mergeSort(left);
        print(left);
    }
    
    
    private static void mergeArray(int[] a ,int left,int mid,int right,int[] tem){
        int i = left;
        int j = mid + 1;
        int k = left;
        
        while(i <= mid && j <= right){
            if(a[i] < a[j]){
                tem[k] = a[i];
                i++;
                k++;
            }else{
                tem[k] = a[j];
                j++;
                k++;
            }
        }
        
        while(i <= mid){
            tem[k] = a[i];
            i++;
            k++;
        }
        
        while(j <= right){
            tem[k] = a[j];
            j++;
            k++;
        }
        
        for(;left <= right;left++){
            a[left] = tem[left];
        }
    }
    
    public static void mergeSort(int[] array){
        mergeSortMethod(array, 0, array.length - 1, new int[array.length]);
    }
    
    private static void mergeSortMethod(int [] array,int start ,int end ,int[] tem){
        if(start < end){
            int mid = (start + end) / 2;
            mergeSortMethod(array, start, mid, tem);
            mergeSortMethod(array, mid + 1, end, tem);
            mergeArray(array, start, mid, end, tem);
        }
    }
    
    
    
    public static void print(int[] array){
        for(int i : array){
            System.out.print(i + " ");
        }
        System.out.println("");
    }
}