二路归并排序 代码实例-阿里云开发者社区

开发者社区> 旭东的博客> 正文

二路归并排序 代码实例

简介:   感觉好久没有写排序程序了,C语言有qsort()函数,C++有sort()函数,java语言有Arrays类(主要这个不是Array)。今天写了一下归并排序还有点费劲呀。晚上回来写写。   归并排序就是采用分治法进行排序:   (1)将一个数组分成小的2个数组分别进行排序;   (2)之后...
+关注继续查看

  感觉好久没有写排序程序了,C语言有qsort()函数,C++有sort()函数,java语言有Arrays类(主要这个不是Array)。今天写了一下归并排序还有点费劲呀。晚上回来写写。

  归并排序就是采用分治法进行排序:

  (1)将一个数组分成小的2个数组分别进行排序;

  (2)之后将分出来的已经拍好序的数组进行合并;

晚上写的java二路归并排序代码如下:

import java.util.Scanner;
public class MergeSort {
    int[] a=null;
    int[] b=null;
    int n;
    Scanner sin=null;
    
    MergeSort()
    {
        a=new int[10000];
        b=new int[10000];
        sin=new Scanner(System.in);
    }
    
    void sort(int start,int end)    //排序a[start...end]
    {
        int mid;
     if(start >= end)    //只有一个元素的时候,直接返回
            return ;
        else
        {
            mid=(end-start)/2;    //将元素分成两半,分别排序
            sort(start,start+mid);
            sort(start+mid+1,end);
            
            //归并两个有序的数组a[start...start+mid]和a[start+mid+1...end]
            merge(start,start+mid,end);    
        }
    }
    
    void merge(int start,int mid,int end)    //归并
    {
        int t=start;
        int i=start,j=mid+1;
        while(i<=mid && j<=end)
        {
            if(a[i]<a[j])
                b[t++]=a[i++];
            else
                b[t++]=a[j++];
        }
        while(i<=mid)
            b[t++]=a[i++];
        while(j<=end)
            b[t++]=a[j++];
        
        for(i=start;i<=end;i++)    //排序后的内容写回a数组的相应位置去
            a[i]=b[i];
    }
    
    void run()
    {
        System.out.print("输入要排序的数的个数:");
        n=sin.nextInt();
        for(int i=0;i<n;i++)
            a[i]=sin.nextInt();
        sort(0,n-1);
        System.out.println("排序结果是:");
        //输入要排序的数据
        for(int i=0;i<n;i++)
            System.out.println(a[i]+"  ");
    }
    
    public static void main(String[] args) {
        new MergeSort().run();
    }
}

 

 

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
排序算法大数据量测试代码
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; using System.Diagnostics; using System.IO; namespace Sort { class Program
825 0
使用FFmpeg新解码API解封装解码音视频(代码实例)
在ffmpeg的源代码中,有新旧版本的编解码接口调用示例,但是demux、mux然后decode、encode的联动起来的接口调用实例并没有,在使用旧版本的编解码接口在编译时会报接口弃用告警信息,所以最好尽快把原有的调用方式切换到新的编解码接口调用方式,告警信息如下: ...
1983 0
PageAdmin CMS网站建设实例:如何制作一个报名表?
PageAdmin CMS网站制作实例:如何制作一个报名表?有时我们根据需求需要制作一些自定义表,该如何去制作呢? 我们以制作一个报名表为例; 登录后台地址,进入后台, 2.在顶部导航中找到系统,并点击,然后在左侧导航中,找到信息表,并点击; 我们会看到一些信息表 3.
1503 0
分享实录 | 阿里巴巴自研代码管理平台技术解密
近日,阿里巴巴旗下企业级一站式DevOps平台——阿里云·云效正式开启公测,为了让广大开发者更好地了解“新云效”,《云效说码》栏目特别策划了《为云研发而生 解密云效公测版专场》系列分享,邀请了5位阿里巴巴技术专家通过视频直播的方式与大家在线交流,分享云效产品的亮点和技术优势。
2805 0
duilib 的IE浏览器控件去边框和去滚动条的代码
转载请说明原出处,谢谢~~         近些天在duilib群里经常有朋友问起,怎么让duilib的IE控件可以去边框,去滚动条的问题,或者是如何去控件IE控件的行为。
1012 0
十大经典排序算法动画与解析,看我就够了!(配代码完全版) | 算法必看系列三十八
排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为 内部排序 和 外部排序 。内部排序是数据记录在内存中进行排序。而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
1430 0
+关注
旭东的博客
从事互联网开发工作,写博客,记录问题与学习支持,并分析
194
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《Nacos架构&原理》
立即下载
《看见新力量:二》电子书
立即下载
云上自动化运维(CloudOps)白皮书
立即下载