前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >归并排序

归并排序

作者头像
热心的社会主义接班人
发布2018-04-27 14:43:21
8100
发布2018-04-27 14:43:21
举报
文章被收录于专栏:cs

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

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

代码语言:javascript
复制
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]);
    }

}

结果

代码语言:javascript
复制
 -8 1 3 5 8 16 26 88

归并排序

代码语言:javascript
复制
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();
        
    }

        
}

结果

代码语言:javascript
复制
 1 288 311 400 5 88 89 100
 1 5 88 89 100 288 311 400

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

大同小异,思路差不多。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018.04.06 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档