归并排序（含树的前序遍历，中序遍历，后续遍历）

小灰灰 2021-01-24 18:16 615阅读 0赞

归并排序是一种分而治之的思想，利用的是递归的方法，在实现上与树的遍历十分相似。

所以我打算，先总结一下树的三种遍历，并于归并排序做对比，加深印象。

** 前序遍历**

(1)若二叉树为空，则为空操作，返回空。  
(2)访问根结点。  
(3)前序遍历左子树。  
(4)前序遍历右子树。

void PreOrderTraverse(BiTree BT)
       {
         if(BT)
         {
            printf("%c",BT->data);              //访问根结点
            PreOrderTraverse(BT->lchild);       //前序遍历左子树
            PreOrderTraverse(BT->rchild);       //前序遍历右子树
         }
       }

**     中序遍历**

(1)若二叉树为空，则为空操作，返回空。  
(2)中序遍历左子树。  
(3)访问根结点。  
(4)中序遍历右子树。

void InOrderTraverse(BiTree BT)
        {
          if(BT)
          {
             InOrderTraverse(BT->lchild);        //中序遍历左子树
             printf("%c",BT->data);              //访问根结点
             InOrderTraverse(BT->rchild);        //中序遍历右子树
          }
        }

** 后序遍历**

(1)若二叉树为空，则为空操作，返回空。  
 (2)后序遍历左子树。  
(3)后序遍历右子树。  
(4)访问根结点。

void PostOrderTraverse(BiTree BT)
         {
           if(BT)
           {
              PostOrderTraverse(BT->lchild);        //后序遍历左子树
              PostOrderTraverse(BT->rchild);        //后序遍历右子树
              printf("%c",BT->data);                //访问根结点
           }
         }

这里我觉的非常有必要对递归，做一下总结，记得当初初次接触递归的时候，觉得非常难以接受，其实，找一个递归深度浅一点的，自己动手，一步一步按照递归的思路，画出过程，就理解了

**1.要解决的问题，可以分成n个相同结构的步骤解决（结构相同，数据不同，下一步的数据，需要上一步的结果）**

**  2.自己调用自己，要想获取上一步的结果，就必须把自己的结果传给下一步**

**  3.递归是一个循环，所以要给出入口，就是第一步的结果，还要有出口，不然就是死循环**

然后先上归并排序的代码

package com.example.eurekaribbonclient.test;
    
    import java.util.Arrays;
    
    /**
     * @ClassName test_2
     * @Description TODO
     * @Author Mr.G
     * @Date 2018/9/18 10:32
     * @Version 1.0
     */
    
    public class test_2 {
       public static void main(String [] args){
           int[] arry={9,8,7,6,5,4,3,2,1};
           int[] temp=new int[arry.length];//避免大量开辟空间
           sort(arry,0,arry.length-1,temp);//入口
           System.out.println(Arrays.toString(temp));
       }
       public static void sort(int[] arry,int left,int right,int[] temp){
           if(left<right){//条件不满足为出口
               int mid=(left+right)/2;
               sort(arry,left,mid,temp);//使左边有序
               sort(arry,mid+1,right,temp);//使右边有序
               combin(arry,left,mid,right,temp);//有序合并左右
           }
       }
       public static void combin(int[] arry,int left,int mid,int right,int[] temp){
           int i=left;
           int j=mid+1;
           int t=0;
           while(i<=mid&&j<=right){
               if(arry[i]<=arry[j]){
                   temp[t++]=arry[i++];
               }else{
                   temp[t++]=arry[j++];
               }
           }
           while(i<=mid){//如果左边有剩余，放到数组里
               temp[t++]=arry[i++];
           }
           while(j<=right){//如果右边有剩余，放到数组里
               temp[t++]=arry[j++];
           }
           t=0;
           while(left<=right){
               arry[left++]=temp[t++];//把数据放回arry[],因为temp会在递归过程被不断使用
           }
       }
    }

![70][]

如果理解还是困难，我们写个小例子一步一步进去看看。

例如 3 2 4 1

第一步会进入 左边排序

3  2

让后继续左边排序

然后右边排序

合并排序

2 3

a\[0\]=2 a\[1\]=3

返回到第一步右边排序

4 1

左边排序

右边排序

合并

1 4

a\[2\]=1 a\[3\]=4

返回到第一步，合并

1 2 3 4

此时 arry和temp的值都是1 2 3 4

递归其实就是压栈和出栈操作，没调用自己一次，就把原来的函数压栈，找到出口就出栈一个，直到栈空，结果也就出来了

所以符合后进先出

然后是分析一波时间复杂度

总时间=分解时间+解决问题时间+合并时间。分解时间就是把一个待排序序列分解成两序列，时间为一常数，时间复杂度o(1).解决问题时间是两个递归式，把一个规模为n的问题分成两个规模分别为n/2的子问题，时间为2T(n/2).合并时间复杂度为o（n）。总时间T(n)=2T(n/2)+o(n).这个递归式可以用递归树来解，其解是o(nlogn).此外在最坏、最佳、平均情况下归并排序时间复杂度均为o(nlogn).从合并过程中可以看出合并排序稳定。   
用递归树的方法解递归式T(n)=2T(n/2)+o(n):假设解决最后的子问题用时为常数c，则对于n个待排序记录来说整个问题的规模为cn。

![SouthEast][]

从这个递归树可以看出，第一层时间代价为cn，第二层时间代价为cn/2+cn/2=cn…..每一层代价都是cn，总共有logn+1层。所以总的时间代价为cn\*(logn+1).时间复杂度是o(nlogn).

[70]: /images/1611512166336.png
[SouthEast]: /images/1611512142929.png