算法（一）之排序算法（七）——归并排序(MergeSort)

上篇有个问题说道，当我们的待排序的数据数据量较大并且是线性结构时用快速排序进行排序操作。但是当我们要排序的数据是链式结构怎么办？这就引入了一个改进的排序方法——归并排序。

归并排序也是八大排序算法之一。它是建立在归并操作上的一种有效的排序算法，所谓归并是指将若干个已排好序的部分合并成一个有序的部分。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，归并排序将两个已排序的表合并成一个表。

这里有个很重要的东西，归并排序的前提：数据已经排好序，就是把两组排好序的数据进行排序。

具体要怎么说我也表达不清楚，现在上一张图，这个图在我看来把归并排序的操作体现的淋漓尽致。

假设我们有一个没有排好序的序列，那么首先我们使用分割的办法将这个序列分割成一个个已经排好序的子序列。然后再利用归并的方法将一个个的子序列合并成排序好的序列。

从上图可以看出，我们首先把一个未排序的序列从中间分割成2部分，再把2部分分成4部分，依次分割下去，直到分割成一个一个的数据，再把这些数据两两归并到一起，使之有序，不停的归并，最后成为一个排好序的序列。

从上图我们还可以看出，分割过程是把原来的数组分割成若干个小数组的过程，然后进行归并。由此可见使用归并排序会有较大的内存开销，开销主要体现在数组的开销。

过程就如上图所示，现在我们通过代码来加深了解;

  //left和right分别代表数组的头尾两个下标
  public static void mergeSort(int array[],int left,int right){
    if(left==right){
        return;
    }else{
        int mid=(left+right)/2;    //相当于二叉树的后序遍历
        mergeSort(array,left,mid);//排好左边  L
        mergeSort(array,mid+1,right);//排好右边  R
        merge(array,left,mid+1,right);//再对左右进行合并 D
    }
  }
  
  //对数组的归并操作
  public static void merge(int[] array,int left,int mid,int right){
    int leftSize=mid-left;
    int rightSize=right-mid+1;  //把mid位置的数据放到右边的数组中
    //生成数组
    int[] leftArray=new int[leftSize];
    int[] rightArray=new int[rightSize];
    //填充左边的数组
    for(int i=left;i<mid;i++){
        leftArray[i-left]=array[i];
    }
    //填充右边的数组
    for(int i=mid;i<=right;i++){
        rightArray[i-mid]=array[i];
    }

    //合并数组
    int i=0;     //左边数组的下标
    int j=0;    //右边数组的下标
    int k=left;    //原来数组的下标
    while(i<leftSize && j<rightSize){    //代表i没有移出去并且j也没有移出去，那就一直比较下去
        if(leftArray[i]<rightArray[j]){
            array[k]=leftArray[i];
            k++;
            i++;
        }else{
            array[k]=rightArray[j];
            k++;
            j++;
        }
    }
    while(i<leftSize){//左边还有数据没用完
        array[k]=leftArray[i];
        k++;
        i++;
    }
    while(j<rightSize){//右边还有数据没用完
        array[k]=rightArray[j];
        k++;
        j++;
    }

  }

从代码上我们可以看出，归并排序就是对数组的分割归并过程，所以我们必须要掌握这个归并数组的过程。然后通过分治思想对待排序的数组进行排序。

现在一直说二叉树的遍历，我们在后面的数据结构文章中会提到。

归并排序的应用场景：数据量大并且是链式存储结构的数据。