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[i]<=b[i]){
      c[k++]=a[i++];
    }
    else{
      c[k++]=b[j++];
    }
  }
  while (i<=a.length){
    c[k++]=a[i++];
  }
  while (j<=b.length){
    c[k++]=b[j++];
  }
}

容易看出，这样的合并算法是高效的，其时间复杂度可达到O(n)。
2.假如有一个无序数组需要排序，但它的两个完全划分的子数组A和B分别有序，借助上述代码，我们也可以很容易实现；
3.那么，如果A,B无序，怎么办呢？可以把它们再分成更小的数组。
4.如此一直划分到最小，每个子数组都只有一个元素，则可以视为有序数组。
5.从这些最小的数组开始，逆着上面的步骤合并回去，整个数组就排好了。
总而言之，归并排序就是使用递归，先分解数组为子数组，再合并数组。

例子
下面举例说明，假如要对数组a={2,1,3,5,2,3}进行排序，那么把数组划分为{2,1,3}和{5,2,3}两个子数组，这两个子数组排序后变为{1,2,3}和{2,3,5}，然后对这两个数组进行归并操作便得到最终的有序数组。代码实现如下：

void sort(int[] a) {
  int[] aux = new int[a.length];  //辅助数组
  mergeSort(a, 0, a.length - 1, aux);
}

void mergeSort(int[] a, int lo, int hi, int[] aux) {
  if (hi <= lo)
    return;
  int mid = lo + (hi - lo) / 2;
  mergeSort(a, lo, mid, aux);
  mergeSort(a, mid + 1, hi, aux);
  merge(a, lo, mid, hi, aux);

}

void merge(int[] a, int lo, int mid, int hi, int[] aux) {
  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 (aux[i] <= aux[j])
      a[k] = aux[i++];
    else
      a[k] = aux[j++];

  }
}

另一种实现：自底向上的归并排序
在上面的实现中，相当于将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。将一个大的数组的排序划分为小数组的排序是自顶向下的排序。还有一种实现是自底向上的排序，即先两两归并，然后四四归并......代码实现如下：

void sort(int[] a) {
  int N = a.length;
  int[] aux = new int[N];
  for (int sz = 1; sz < N; sz += sz) {
    for (int lo = 0; lo < N - sz; lo += sz + sz) {
      //在每轮归并中，最后一次归并的第二个子数组可能比第一个子数组要小
      merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1), aux);
    }
  }
}
赞 (0)

相关推荐

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

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

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

  • 深入探究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排序算法总结之归并排序

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

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

  • 浅析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二路归并排序示例分享

    归并排序就是采用分治法进行排序: (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编程中实现归并排序算法的实例教程

    算法概述/思路 归并排序是基于一种被称为"分治"(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编程中实现调用js方法分析

    本文实例讲述了java编程中实现调用js方法.分享给大家供大家参考,具体如下: /* * 加载脚本引擎,并在java中调用js方法 */ public void test2() { ScriptEngineManager manager = new ScriptEngineManager(); ScriptEngine engine = manager.getEngineByName("javascript"); try { String str="2&1"

  • 深入理解Java编程中异常处理的优劣

    Java编程中的异常处理是一个很常见的话题了,几乎任何一门介绍性的Java课程都会提到异常处理.不过,我认为很多人其实没有真正掌握正确处理异常情况的方法和策略,最多也就不过了解个大概,知道概念.我想对三种不同程度和质量的Java异常处理进行了讨论,所阐述的处理异常的方式按手法的高下分为:好,不好和恶劣三种.同时提供了一些解决这些问题的技巧.首先解释一些java异常处理中必须搞清楚的定义和机制.Java语言规范将自Error类或RuntimeException类衍生出来的任何违例都称作"不可检查&

  • Java编程实现轨迹压缩算法开放窗口实例代码

    轨迹压缩算法 场景描述 给定一个GPS数据记录文件,每条记录包含经度和维度两个坐标字段,根据距离阈值压缩记录,将过滤后的所有记录的经纬度坐标构成一条轨迹 算法描述 这种算法的用处还是相当广泛的. 轨迹压缩算法分为两大类,分别是无损压缩和有损压缩,无损压缩算法主要包括哈夫曼编码,有损压缩算法又分为批处理方式和在线数据压缩方式,其中批处理方式又包括DP(Douglas-Peucker)算法.TD-TR(Top-Down Time-Ratio)算法和Bellman算法,在线数据压缩方式又包括滑动窗口.

  • java编程中自动拆箱与自动装箱详解

    什么是自动装箱拆箱 基本数据类型的自动装箱(autoboxing).拆箱(unboxing)是自J2SE 5.0开始提供的功能. 一般我们要创建一个类的对象实例的时候,我们会这样: Class a = new Class(parameter); 当我们创建一个Integer对象时,却可以这样: Integer i = 100; (注意:不是 int i = 100; ) 实际上,执行上面那句代码的时候,系统为我们执行了:Integer i = Integer.valueOf(100); (感谢@

  • 浅谈Java编程中string的理解与运用

    一,"=="与equals() 运行以下代码,如何解释其输出结果? public class StringPool { public static void main(String args[]) { String s0="Hello"; String s1="Hello"; String s2="He"+"llo"; System.out.println(s0==s1);//true System.out

  • Java编程中的构造函数详细介绍

    本文主要是为新手.对java语言感兴趣的人和那些没有系统学习过java基础知识的人进行一个总结,在文章中对构造函数进行了较为详细的说明和讨论,也包含了我个人对于java面向对象中构造函数的一些看法.希望走在java学习道路上的同行者可以有一个较为清晰的认知和理解.当然仅为个人观点,水平有限,不足之处,还请大家多多指出,互相交流学习. 1.构造函数的概念 很多java新手谈到构造函数就会犯晕,我们先来看看什么是构造函数. 首先,构造函数是函数的一种特殊形式,特殊在哪里?构造函数中不需要定义返回类型

  • Java编程中避免equals方法的隐藏陷阱介绍

    摘要 本文描述重载equals方法的技术,这种技术即使是具现类的子类增加了字段也能保证equal语义的正确性. 在<Effective Java>的第8项中,Josh Bloch描述了当继承类作为面向对象语言中的等价关系的基础问题,要保证派生类的equal正确性语义所会面对的困难.Bloch这样写到: 除非你忘记了面向对象抽象的好处,否则在当你继承一个新类或在类中增加了一个值组件时你无法同时保证equal的语义依然正确 在<Programming in Scala>中的第28章演示

  • Java编程中实现Condition控制线程通信

    java中控制线程通信的方法 1.传统的方式:利用synchronized关键字来保证同步,结合wait(),notify(),notifyAll()控制线程通信.不灵活. 2.利用Condition控制线程通信,灵活. 3.利用管道pipe进行线程通信,不推荐 4.利用BlockingQueue控制线程通信 本文就讲解利用Condition控制线程通信,非常灵活的方式. Condition类是用来保持Lock对象的协调调用. 对Lock不了解的可以参考:Java线程同步Lock同步锁代码示例

  • java语言实现权重随机算法完整实例

    java语言实现权重随机算法完整实例

    前言 现在app就是雨后春笋,嗖嗖的往外冒啊,有经验的.没经验的.有资历的.没资历的都想着创业,创业的90%以上都要做一个app出来,好像成了创业的标配. 做了app就得推广啊,怎么推,发券送钱是最多用的被不可少的了,现在好多产品或者运营都要求能够随机出优惠券的金额,但是呢又不能过于随机,送出去的券都是钱吗,投资人的钱,是吧. 所以,在随机生成的金额中就要求,小额度的几率要大,大额度的几率要小,比如说3元的70%,5块的25%,10块的5%,这个样子的概率去生成优惠券,这个怎么办呢? 对于上述的

随机推荐