1.2归并排序

1.输入与输出

输入：需要排序的数组。

输出：排好序的数组。

2.算法思想

归并排序采用了“分治”的思想。在希尔排序中数组被等距离的分成了一个个的小数组。而在归并排序中，程序直接按数组序号将其平分为A B两组，递归下去继续分割，直到分为单独的元素为一组。这样的情况下我们可以把每一组看做一个单独的有序数组。再一一进行合并。

两有序数组合并时只需观察它们的第一个数字，取出较小的并在原数组中删除，若有一数组为空，直接将另一数组元素按顺序落下。便可合并完成。

3.伪代码及注释

代码的主体部分主要分为两个步骤进行实现

第一个步骤：将数组中的元素递归的分为一个个小数组，直到分为单个元素为止。

第二个步骤：将相邻的两个小数组进行合并操作

执行的顺序类似于完全二叉树的后序遍历，程序先分离到底，分离出最左边的第一个元素，然后找相邻的一个，再将两数组合并。

算法实现过程.gif

4.java代码实现

public class mergeSort{
public static void main(String args[]){
    int[] text = {1,7,9,8,4,5,2,6,3,3};
    ms(text);
    show(text);
           }    
public static void ms(int[] a,int hi,int lo,int[] temp){
    int mid = 0;
    if( hi < lo ){       
       mid = (hi+lo)/2;
       ms(a,hi,mid,temp);
       ms(a,mid+1,lo,temp);
       merge(a,hi,mid,lo,temp);
    }
}
public static void ms(int[]a){   
  int[] temp = new int[a.length];
  ms(a,0,a.length-1,temp);
}
public static void merge(int[] a,int hi,int mid,int lo,int[] temp){  
    int i,j,k;
    i = hi;
    j = mid+1;
    k = 0;       
    while(i <= mid && j<=lo){
        if(a[i]<a[j]) temp[k++] = a[i++];
        else temp[k++] = a[j++];}
    while(i<=mid){        
        temp[k++] = a[i++];        
    }     
    while(j<=lo){
        temp[k++] = a[j++];
    }    
    for (i = 0; i < k; i++)
        a[hi + i] = temp[i]; }


   public static void show(int []a){   
    for(int i=0;i<a.length;i++)
       System.out.print(a[i]+" ");
}
}

5.复杂度

归并排序的最好、最坏和平均时间复杂度都是O(nlogn)，稳定性不言而明。

空间复杂度是O(n)。

6.优缺点及适用范围

缺点：归并排序算法比较占用内存，需要有额外的内存空间提供缓存。

优点：相比于传统排序算法效率高且相比于快速排序时间消耗较稳定的排序算法。