归并排序

归并排序，采用分治法。首先采用递归，把数组分成一小段有序，然后再把有序的数组一一合并。

首先看看，把有序的二个数组，合成一个的算法。

package day20180406;

public class GuibingDem {

    public static void main(String[] args) {
    
        int[] test1= {1,3,5};
        int[] test2= {-8,8,16,26,88};
        int[] c=new int[8];
        hebing(test1,test2,c);
        print(c);
    }
    

// 把二个有序的数组合并   
    static void hebing(int[] a,int[] b,int[] c)
    {
        int i=0,j=0;
        int k=0;
        while(i<a.length&&j<b.length)
        {
            if(a[i]<b[j])
            {
                c[k]=a[i];
                k++;
                i++;
            }else
            {
                c[k]=b[j];
                k++;
                j++;
            }
            
        }
        
    while(i<a.length)
    {
        c[k]=a[i];
        k++;
        i++;
    }
        
    while(j<b.length)
    {
        c[k++]=b[j++];
    }
    
    }
    
    static void print(int[] arry)
    {   
        
        for(int i=0; i<arry.length; i++)
        System.out.print(" "+arry[i]);
    }

}

结果

 -8 1 3 5 8 16 26 88

归并排序

package day20180410;

import java.util.ArrayList;

public class DuipaiDem {

    public static void main(String[] args) {
          int[] arry= {1,288,311,400,5,88,89,100};
          int[] b=new int[arry.length];
          System.out.println();
          display(arry);
      sort(arry,0,arry.length-1);
         display(arry);
     //    addSort(arry,b,0,arry.length/2,arry.length-1);
     //    display(b);
          
    }
    
    
 //归并排序
    static void sort(int[] arr,int left,int right)
    {
        int mid;
        int[] num=new int[arr.length];
        if(left==right)
        {
            return ;
        }else {
            mid=(left+right)/2;
            //左边归并排序
            sort(arr,left,mid);
            //右边归并排序
            sort(arr,mid+1,right);
            //合并有序的子数组。
            addSort(arr,num,left,mid,right);
            
        }
        for(int i=left; i<right+1; i++)
        {
            arr[i]=num[i];
        }
    
    }
    
    
    //数组合并
    static void  addSort(int[] a,int[] b,int left,int med,int right)
    {
        int i=left,j=med+1,k=left;
        
     while(i<=med&&j<=right)
     {
        if(a[i]<a[j])
        {
            b[k++]=a[i++];
        }else
        {
        //这里写太快了，写成b[k++]=b[j++];导致，bug了半个多小时
            b[k++]=a[j++];
        }
          
     }
     
     while(i<=med)
     {
         b[k++]=a[i++];
     }
     while(j<=right)
     {
         b[k++]=a[j++];
     }
     
    /*

     for(int m=left; m<right+1; m++)
    
     {
         a[m]=b[m];
     }
     
     */
    }
    
    //打印数组
    static void display(int[] a)
    {
        for(int num:a)
        {
            System.out.print(" "+num);
        }
        
        System.out.println();
        
    }

        
}

结果

 1 288 311 400 5 88 89 100
 1 5 88 89 100 288 311 400

相关文章
归并排序原理及Java实现
Java实现归并排序

大同小异，思路差不多。