归并排序

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

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

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实现归并排序

大同小异,思路差不多。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

【Go 语言社区】Golang 语言学习-变量

注:go语言中,不要求语句末尾加分号,这点和python类似。 注:go语言中,不允许定义没有用到的变量,否则报错,就像import一个没用到的package会...

2737
来自专栏云霄雨霁

Java--lambda(λ)表达式

2376
来自专栏黑泽君的专栏

java基础学习_基础语法(下)01_day05总结

============================================================================= ==...

961
来自专栏python学习指南

Python爬虫(十)_正则表达式

本篇将介绍python正则表达式,更多内容请参考:【python正则表达式】 什么是正则表达式 正则表达式,又称规则表达式,通常被用来检索、替换那些符合某...

2666
来自专栏aCloudDeveloper

const特性总结(不断更新)

作者:bakari  时间:2012.6.5 1、指向const对象的指针---const int *cptr; i、在此,cptr是指向int类型的const...

1988
来自专栏逆向技术

C语言第八讲,指针*

            C语言第八讲,指针* 一丶简单理解指针 说到指针,很多人都说是C语言的重点. 也说是C语言的难点. 其实指针并不是难.而是很多人搞不清地...

3746
来自专栏编程

对Python中的类做简要的分析

在Python中,定义类是通过class关键字,class后面紧接着是类名,即Student,类名通常是大写开头的单词,紧接着是(object),表示该类是从哪...

20110
来自专栏Spark学习技巧

Java泛型详解——绝对是对泛型方法讲解最详细的,没有之一!

ArrayList可以存放任意类型,例子中添加了一个String类型,添加了一个Integer类型,再使用时都以String的方式使用,因此程序崩溃了。为了解决...

1852
来自专栏北京马哥教育

Python 变量类型详解

豌豆贴心提醒,本文阅读时间5分钟,文末有秘密! ? 文 | 豌豆 图 | 来源网络 变量存储在内存中的值。这就意味着在创建变量时会在内存中开辟一个空...

4274
来自专栏http://www.cnblogs.com

python3 re模块

一.常用正则表达式符号和语法: '.' 匹配所有字符串,除\n以外 ‘-’ 表示范围[0-9] '*' 匹配前面的子表达式零次或多次。要匹配 * 字符,请使用 ...

47912

扫码关注云+社区

领取腾讯云代金券