归并排序

归并排序

归并排序的时间复杂度是O(n*log2n)，是稳定的

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

首先思考一个问题，已经排序的两个数组如何融合为一个有序数组
数组a，数组b，b中的第一个与a中的第一个比较，小的那个放到临时数组c中，一旦数组a或者b已经遍历完了，那么另外一个剩下的数组全部放到临时数组即可

1.融合两个已经排序的数组片段

融合两个已经排序的数组段代码如下：

/**
*a为排序数组，left为已排序左片段的下标，mid为已排序左片段的最后一个下标
*，right为已排序的右片段的最后一个下标，tem为临时数组
*
**/
private static void mergeArray(int[] a ,int left,int mid,int right,int[] tem){
        //i为待会要进行比较的左数组的游标，j为右数组的游标，k为临时数组的游标
        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循环只会执行其一，因为只可能出现一个片段有剩余
        while(j <= right){
            tem[k] = a[j];
            j++;
            k++;
        }
        
        //把临时数组放回到原数组
        for(;left <= right;left++){
            a[left] = tem[left];
        }
    }

2.递归划分出已排序的两个数组片段

如何递归划分出已排序的两个数组片段？
如果那个数组片段只有一个元素，就可以看成它是有序的，以下代码递归出这个片段：

    private static void mergeSortMethod(int [] array,int start ,int end ,int[] tem){
        //数组元素大于1的时候才进行递归分割。等于1就直接有序了
        if(start < end){
            //将一个数组分为两段，mid为左边的最后一个下标
            int mid = (start + end) / 2;
            //对左边再进行分割
            mergeSortMethod(array, start, mid, tem);
            //对右边再进行分割
            mergeSortMethod(array, mid + 1, end, tem);
            //归并两个已排序数组
            mergeArray(array, start, mid, end, tem);
        }
    

当片段长度为1的数组进入上述方法时候，递归停止，然后进行第一次的方法调用

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

然后继续上一层的递归出栈。最后完成整个调用。

3.调用mergeArray()方法：

public static void mergeSort(int[] array){
                //这场的临时数组用的是同一个，导致空间复杂度是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("");
    }
}