算法学习总结(四)：归并排序

一、算法分析

　　归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

二、算法描述

　　归并排序具体算法描述如下(递归版本)：

       1、Divide: 把长度为n的输入序列分成两个长度为n/2的子序列。

       2、Conquer: 对这两个子序列分别采用归并排序。

       3、Combine: 将两个排序好的子序列合并成一个最终的排序序列。

　　归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(N*logN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。

最差时间复杂度	O(n log n)
最优时间复杂度	O(n)
平均时间复杂度	O(n log n)
最差空间复杂度	需要辅助空间O(n)

三、算法图解

四、示例代码

public class MergeSort {
    public int[] mergeSort(int[] A, int n) {
        // write code here
       sort(A,0,n-1);
       return A;
    }
     
        public void sort(int[] data,int left,int right){
            if(left<right){
                int middle=(left+right)/2;
                //划分左右
                sort(data,left,middle);
                   sort(data,middle+1,right);
                //合并左右
                merge(data,left,middle,right);
            }
        }
        
        //合并左右两个子数组
        public void merge(int[] data,int left,int middle,int right){
            //临时数组
            int[] tempArr=new int[right-left+1];
            //左边数组游标
            int leftIndex=left;
            //右边数据游标
            int rightIndex=middle+1;
            //临时数组游标
            int tempIndex=0;
            
            while(leftIndex<=middle&&rightIndex<=right){
                //临时数组选取左、右子数组中小数值
               if(data[leftIndex]<data[rightIndex]){
                   tempArr[tempIndex++]=data[leftIndex++];
               }else{
                   tempArr[tempIndex++]=data[rightIndex++];
               }
            }
            //剩余的直接放入
            while(leftIndex<=middle){
                   tempArr[tempIndex++]=data[leftIndex++];
            }
            //剩余的直接放入
            while(rightIndex<=right){
                   tempArr[tempIndex++]=data[rightIndex++];
            }
            //将临时数组放回原数组相应位置
            int temp=0;
            while((temp+left)<=right){
                data[left+temp]=tempArr[temp];
                temp++;
            }
        }
}