java 算法之归并排序详解及实现代码

java 算法之归并排序详解

一、思想

归并排序：将一个数组排序，可以先（递归地）将它分成两半部份分别排序，然后将结果归并起来；

二、概念

归并：将两个有序的数组归并成一个更大的有序数组；

三、特点

优点：能够保证将任意长度为N的数组排序所需要的时间和NlogN成正比；

缺点：需要额外的空间和N成正比；

四、实现方法

将两个不同的有序数组归并到第三个数组中；

先将前半部分排序，在将后半部分排序，然后在数组中移动元素而不需要使用额外的空间；

五、代码

/**
 * 归并排序
 *
 * @author pengcx
 *
 */
public class Merge extends Sort {
  /** 归并所需的辅助数组 */
  private static Comparable[] aux;  

  public static void main(String[] args) {
    String[] a = { "d", "a", "w", "b", "q" };
    Merge.sort(a);
    show(a);
  }  

  public static void sort(Comparable[] a) {
    aux = new Comparable[a.length];
    sort(a, 0, a.length - 1);
  }  

  /**
  * 排序数组的a[lo]至a[hi]元素
  *
  * @param a
  *      数组a
  * @param lo
  *      最小元素位置lo
  * @param hi
  *      最大元素位置hi
  */
  private static void sort(Comparable[] a, int lo, int hi) {
    if (hi <= lo) {
      return;
    }  

    // 计算数组中间位置
    int mid = lo + (hi - lo) / 2;
    // 排序数组a左边的元素
    sort(a, lo, mid);
    // 排序数组a右边的元素
    sort(a, mid + 1, hi);
    // 合并数组a左边和右边的元素
    merge(a, lo, mid, hi);
  }  

  /**
  * 将数组a的a[lo]至a[mid]的元素与a[mid]至a[hi]的元素合并
  *
  * @param a
  *      合并的数组a
  * @param lo
  *      最小数组元素lo
  * @param mid
  *      中间元素位置mid
  * @param hi
  *      最大元素位置hi
  */
  public static void merge(Comparable[] a, int lo, int mid, int hi) {
    int i = lo, j = mid + 1;  

    for (int k = lo; k <= hi; k++) {
      aux[k] = a[k];
    }  

    for (int k = lo; k <= hi; k++) {
      // 如果左边的元素用尽，取右边的元素
      if (i > mid) {
        a[k] = aux[j++];
      }
      // 如果右边的元素用尽，取左边的元素
      else if (j > hi) {
        a[k] = aux[i++];
      }
      // 如果右半边的当前元素小于左半边的当前元素，取右半边元素
      else if (less(aux[j], aux[i])) {
        a[k] = aux[j++];
      }
      // 如果右半边的当前元素大于等于左半边的当前元素，取左半边元素
      else {
        a[k] = aux[i++];
      }
    }
  }
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

  • 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 归并排序算法

    浅析java 归并排序算法

    归并排序(Merge)是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用. 将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为2-路归并. 归并排序算法稳定,数组需要O(n)的额外空间,链表需要O(log(n))

  • 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排序算法总结之归并排序.分享给大家供大家参考.具体分析如下: 归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作.和快速排序类似,让我们一起来看,归并在Java中的实现. 归并排序(Merge)是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的

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

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

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

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

  • 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代码实现

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

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

  • Java编程中实现归并排序算法的实例教程

    算法概述/思路 归并排序是基于一种被称为"分治"(divide and conquer)的策略.其基本思路是这样的: 1.对于两个有序的数组,要将其合并为一个有序数组,我们可以很容易地写出如下代码: //both a and b is ascend. public void merge(int[] a, int[] b, int[] c){ int i=0,j=0,k=0; while (i<=a.length && j<=b.length){ if (a[

  • java 算法之归并排序详解及实现代码

    java 算法之归并排序详解 一.思想 归并排序:将一个数组排序,可以先(递归地)将它分成两半部份分别排序,然后将结果归并起来: 二.概念 归并:将两个有序的数组归并成一个更大的有序数组: 三.特点 优点:能够保证将任意长度为N的数组排序所需要的时间和NlogN成正比: 缺点:需要额外的空间和N成正比: 四.实现方法 将两个不同的有序数组归并到第三个数组中: 先将前半部分排序,在将后半部分排序,然后在数组中移动元素而不需要使用额外的空间: 五.代码 /** * 归并排序 * * @author

  • java多线程编程技术详解和实例代码

     java多线程编程技术详解和实例代码 1.   Java和他的API都可以使用并发. 可以指定程序包含不同的执行线程,每个线程都具有自己的方法调用堆栈和程序计数器,使得线程在与其他线程并发地执行能够共享程序范围内的资源,比如共享内存,这种能力被称为多线程编程(multithreading),在核心的C和C++语言中并不具备这种能力,尽管他们影响了JAVA的设计. 2.   线程的生命周期 新线程的生命周期从"新生"状态开始.程序启动线程前,线程一直是"新生"状态:

  • java读取resources文件详解及实现代码

    java读取resources文件详解及实现代码 Java项目中,经常需要将资源文件打包放在项目中,然后在项目中去读取对应的文件. 实现代码: String str = ReadFile.read(getClass().getResourceAsStream("sence/"+file)); public static String read(InputStream inputStream) { BufferedReader reader = null; String laststr

  • java 汉诺塔详解及实现代码

    java 汉诺塔详解及实现代码

    java 汉诺塔详解及实现代码 实现效果图 打印的方法在 moveTheTopOne() 方法中被调用,调用该方法前打印出移动的方向--从X号塔往Y号塔 汉诺塔要求:将第一座塔上的所有盘子,借助第二座塔,全部搬运到第三座塔上. 规则:一次只能搬运一个盘子,不准将大盘子落在小盘子上.  汉诺塔实现代码: public class NewHanoi { public static int tiers = 4; // tiers 层数 private static List<String> pago

  • Java 垃圾回收机制详解及实例代码

     Java 垃圾回收机制详解 乍一看,垃圾回收所做的事情应当恰如其名--查找并清除垃圾.事实上却恰恰相反.垃圾回收会跟踪所有仍在使用的对象,然后将剩余的对象标记为垃圾.牢记了这点之后,我们再来深入地了解下这个被称为"垃圾回收"的自动化内存回收在JVM中到底是如何实现的. 手动管理内存 在介绍现代版的垃圾回收之前,我们先来简单地回顾下需要手动地显式分配及释放内存的那些日子.如果你忘了去释放内存,那么这块内存就无法重用了.这块内存被占有了却没被使用.这种场景被称之为内存泄露. 下面是用C写

  • Java中初始化块详解及实例代码

    Java中初始化块详解 在Java中,有两种初始化块:静态初始化块和非静态初始化块. 静态初始化块:使用static定义,当类装载到系统时执行一次.若在静态初始化块中想初始化变量,那仅能初始化类变量,即static修饰的数据成员. 非静态初始化块:在每个对象生成时都会被执行一次,可以初始化类的实例变量. 非静态初始化块会在构造函数执行时,且在构造函数主体代码执行之前被运行. 括号里的是初始化块,这里面的代码在创建Java对象时执行,而且在构造器之前执行! 其实初始化块就是构造器的补充,初始化块是

  • java DataInputStream和DataOutputStream详解及实例代码

    java DataInputStream和DataOutputStream详解 操作基本数据类型的流 DataInputStream DataOutputStream import java.io.DataInputStream; import java.io.DataOutputStream; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.IOException; public c

  • Java Process类的详解及实例代码

    Java Process类的详解 前言: 今天用了下Java.lang.Process类,只是初步的学习,并没有深入实践,因为感觉它的用途并不是很大,偶尔才可能用上,如果要经常使用它的人可以自行参考JDk文档. 对Process类的简要说明: Process类是一个抽象类,方法都是抽象的,它封装了一个进程,也就是一个可执行的程序  该类提供进程的输入.执行输出到进程.等待进程的完成和检查进程的退出状态及销毁进程的方法 ProcessBuilder.start()和Runtime.exec方法创建

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

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

  • JAVA十大排序算法之归并排序详解

    JAVA十大排序算法之归并排序详解

    目录 归并排序 怎么分 怎么治 代码实现 时间复杂度 算法稳定性 总结 归并排序 归并,指合并,合在一起.归并排序(Merge Sort)是建立在归并操作上的一种排序算法.其主要思想是分而治之.什么是分而治之?分而治之就是将一个复杂的计算,按照设定的阈值进行分解成多个计算,然后将各个计算结果进行汇总.即"分"就是把一个大的通过递归拆成若干个小的,"治"就是将分后的结果在合在一起. 若将两个有序集合并成一个有序表,称为2-路归并,与之对应的还有多路归并. 怎么分 对于

随机推荐