java二路归并排序示例分享

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

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

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

代码如下:

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();
    }
}

赞 (0)

相关推荐

  • 深入探究TimSort对归并排序算法的优化及Java实现

    简介 MergeSort对已经反向排好序的输入时复杂度为O(n^2),而timsort就是针对这种情况,对MergeSort进行优化而产生的,平均复杂度为n*O(log n),最好的情况为O(n),最坏情况n*O(log n).并且TimSort是一种稳定性排序.思想是先对待排序列进行分区,然后再对分区进行合并,看起来和MergeSort步骤一样,但是其中有一些针对反向和大规模数据的优化处理. 归并排序的优化思想 归并排序有以下几点优化方法: 和快速排序一样,对于小数组可以使用插入排序或者选择排

  • 归并排序的原理及java代码实现

    归并排序的原理及java代码实现

    概述 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序采用的是递归来实现,属于"分而治之",将目标数组从中间一分为二,之后分别对这两个数组进行排序,排序完毕之后再将排好序的两个数组"归并"到一起,归并排序最重要的也就是这个"归并"的过程,归并的过程中需要额外的跟需要归并的两个数组长度一致的空间. 效果图: 步骤 申请空间,

  • java数据结构排序算法之归并排序详解

    本文实例讲述了java数据结构排序算法之归并排序.分享给大家供大家参考,具体如下: 在前面说的那几种排序都是将一组记录按关键字大小排成一个有序的序列,而归并排序的思想是:基于合并,将两个或两个以上有序表合并成一个新的有序表 归并排序算法:假设初始序列含有n个记录,首先将这n个记录看成n个有序的子序列,每个子序列长度为1,然后两两归并,得到n/2个长度为2(n为奇数的时候,最后一个序列的长度为1)的有序子序列.在此基础上,再对长度为2的有序子序列进行亮亮归并,得到若干个长度为4的有序子序列.如此重

  • java 基本算法之归并排序实例代码

    java 基本算法之归并排序实例代码 原理:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表, * 即把待排序序列分为若干个子序列,每个子序列是有序的.      * 然后再把有序子序列合并为整体有序序列. 实例代码: public class MergeSort { /** * * * * @param args */ public static void main(String[] args) { int a[] = { 49, 38, 65, 97, 76, 13,

  • java实现归并排序算法

    java实现归并排序算法

    归并排序算法思想: 分而治之(divide - conquer);每个递归过程涉及三个步骤 第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素. 第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作 第三, 合并: 合并两个排好序的子序列,生成排序结果. public static void mergeSort(int[] a, int[] tmp, int left, int right) { if (left < righ

  • java 归并排序的实例详解

    java 归并排序的实例详解 归并排序 归并排序,指的是将两个已经排序的序列合并成一个序列的操作. 归并操作的过程如下: 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 设定两个指针,最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 重复步骤3直到某一指针到达序列尾 将另一序列剩下的所有元素直接复制到合并序列尾 Java代码 /** * 归并排序 * * @param ts */ @SuppressWa

  • Java经典排序算法之归并排序详解

    Java经典排序算法之归并排序详解

    一.归并排序 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 归并过程为:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1:否则将第二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直

  • java二路归并排序示例分享

    归并排序就是采用分治法进行排序: (1)将一个数组分成小的2个数组分别进行排序: (2)之后将分出来的已经拍好序的数组进行合并: 复制代码 代码如下: 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[

  • java操作mongodb示例分享

    复制代码 代码如下: package mymaven; import java.net.UnknownHostException;  import java.util.Set; import com.mongodb.BasicDBObject;  import com.mongodb.DB;  import com.mongodb.DBCollection;  import com.mongodb.DBCursor;  import com.mongodb.DBObject;  import c

  • java排序去重示例分享

    复制代码 代码如下: package action;import java.util.Arrays;import java.util.TreeSet;public class test { /**  * @param args  */ public static void main(String[] args) {  String strs = "ZZZ BBB AAA OOO ZZZ AAA ZZZ BBB AAA ZZZ AAA VVV OOO CCC DDD CCC CCC KKK BBB

  • 简单的java读取文件示例分享

    可以作如下理解: 首先获得一个文件句柄.File file = new File(); file即为文件句柄.两人之间连通电话网络了.接下来可以开始打电话了 通过这条线路读取甲方的信息:new FileInputStream(file) 目前这个信息已经读进来内存当中了.接下来需要解读成乙方可以理解的东西 既然你使用了FileInputStream().那么对应的需要使用InputStreamReader()这个方法进行解读刚才装进来内存当中的数据 解读完成后要输出呀.那当然要转换成IO可以识别

  • java 2d画图示例分享(用java画图)

    Java 2D API通过扩展抽象窗口工具箱(AWT),为Java程序提供了二维图像,文本和图形的功能.这个复杂的渲染包支持线形图像,文本和图形,为富用户界面,复杂绘图程序和图像处理器开发者提供灵活的,功能强大的框架.Java 2D对象出现在一个平面中,称为用户坐标系空间,和设备坐标系空间.当对象在屏幕或打印机中渲染时,用户空间坐标系被转换成设备空间坐标系. 复制代码 代码如下: import java.awt.BasicStroke;import java.awt.Color;import j

  • java音频播放示例分享(java如何播放音频)

    这是一份精简后的代码,能够支持的格式十分有限. 复制代码 代码如下: package com.hongyuan.test; import java.io.File;import java.io.IOException; import javax.sound.sampled.AudioFormat;import javax.sound.sampled.AudioInputStream;import javax.sound.sampled.AudioSystem;import javax.sound

  • java字符串反转示例分享

    思路: 将字符串变成数组,对数组反转将反转后的数组变成字符串只要将反转的部分的开始和结束的位置作为参数传递即可 复制代码 代码如下: class reverse_String{    public static void main (String[] args){        String s1 = "      java php .net    ";        String s2 = reverseString(s1);        System.out.println(s2

  • java控制台输入示例分享

    java控制台输入有如下几个方法 1.JDK 1.4 及以下版本读取的方法 JDK 1.4 及以下的版本中要想从控制台中输入数据只有一种办法,即使用System.in获得系统的输入流,再桥接至字符流从字符流中读入数据.只能读取字符串,若需要读取其他类型的数据需要手工进行转换.代码如下: 复制代码 代码如下: BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String str = null;try{

  • java右下角弹窗示例分享

    复制代码 代码如下: package com.wolf.action; import java.awt.BorderLayout;import java.awt.Dimension;import java.awt.Toolkit;import java.awt.event.ActionEvent;import java.awt.event.ActionListener; import javax.swing.JDialog;import javax.swing.Timer; public cla

  • java反射使用示例分享

    复制代码 代码如下: public class ReflexTest { public static void main(String[] args)      throws ClassNotFoundException, NoSuchMethodException, SecurityException,     IllegalAccessException, IllegalArgumentException, InvocationTargetException,      Instantiat

随机推荐