java 归并排序的实例详解

java 归并排序的实例详解

归并排序

归并排序，指的是将两个已经排序的序列合并成一个序列的操作。

归并操作的过程如下：

  • 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  • 设定两个指针，最初位置分别为两个已经排序序列的起始位置
  • 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  • 重复步骤3直到某一指针到达序列尾
  • 将另一序列剩下的所有元素直接复制到合并序列尾

Java代码

/**
 * 归并排序
 *
 * @param ts
 */
@SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>> void mergeSort(T[] ts) { 

  // 辅助空间
  T[] tempArray = (T[]) new Comparable[ts.length]; 

  mergeSort(ts, tempArray, 0, ts.length - 1);
} 

/**
 * 递归
 */
private static <T extends Comparable<? super T>> void mergeSort(T[] ts, T[] tempArray, int left, int right) { 

  if (left < right) { 

    int center = (left + right) / 2; 

    mergeSort(ts, tempArray, left, center); 

    mergeSort(ts, tempArray, center + 1, right); 

    // 左右合并
    merge(ts, tempArray, left, center + 1, right); 

  } 

} 

/**
 * 合并
 */
private static <T extends Comparable<? super T>> void merge(T[] ts, T[] tempArray, int leftPos, int rightPos, int rightEnd) {
  int leftEnd = rightPos - 1;
  int temPos = leftPos;
  int numElements = rightEnd - leftPos + 1; 

  while (leftPos <= leftEnd && rightPos <= rightEnd)
    //比较放到辅助空间
    if (ts[leftPos].compareTo(ts[rightPos]) <= 0)
      tempArray[temPos++] = ts[leftPos++];
    else
      tempArray[temPos++] = ts[rightPos++]; 

  while (leftPos <= leftEnd)
    tempArray[temPos++] = ts[leftPos++]; 

  while (rightPos <= rightEnd)
    tempArray[temPos++] = ts[rightPos++]; 

  //考回原数组,此处最好用System.arraycopy优化
  for (int i = 0; i < numElements; i++, rightEnd--)
    ts[rightEnd] = tempArray[rightEnd];
}

 复杂度：O(n log n)

比较操作的次数介于(n log n)/2和n log n - n + 1。 赋值操作的次数是(2nlogn)。

归并算法的空间复杂度为：Θ(n)

 稳定性：稳定 

扩展：

在java中，当执行一次泛型排序时，进行一次元比较可能是昂贵的，但是移动元素则是省时间的。归并排序使用所有的流行的排序算法中最少的比较次数，因此是使用java的通用排序算中的上好的选择。

以上使用java 使用归并排序的简单实例，有关java算法知识本站还有很多，大家可以搜索，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

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

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

  • java 中归并排序算法详解

    java 中归并排序算法详解

    java 中归并排序算法详解 归并排序算法,顾名思义,是一种先分再合的算法,其算法思想是将要排序的数组分解为单个的元素,每个元素就是一个单个的个体,然后将相邻的两个元素进行从小到大或从大到小的顺序排序组成一个整体,每个整体包含一到两个元素,然后对相邻的整体继续"合"并,因为每个整体都是排过序的,因而可以采用一定的算法对其进行合并,合并之后每个整体包含三到四个元素,继续对相邻的整体进行合并,直到所有的整体都合并为一个整体,最终得到的整体就是将原数组进行排序之后的结果. 对于相邻的整体,其

  • 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经典排序算法之归并排序详解

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

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

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

  • java 归并排序的实例详解

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

  • Java多线程ForkJoinPool实例详解

    引言 java 7提供了另外一个很有用的线程池框架,Fork/Join框架 理论 Fork/Join框架主要有以下两个类组成. * ForkJoinPool 这个类实现了ExecutorService接口和工作窃取算法(Work-Stealing Algorithm).它管理工作者线程,并提供任务的状态信息,以及任务的执行信息 * ForkJoinTask 这个类是一个将在ForkJoinPool执行的任务的基类. Fork/Join框架提供了在一个任务里执行fork()和join()操作的机制

  • java 抽象类的实例详解

    java 抽象类的实例详解 前言: 什么是抽象类?这名字听着就挺抽象的,第一次听到这个名字还真有可能被唬住.但是,就像老人家所说的,一切反动派都是纸老虎,一切有着装x名字的概念也是纸老虎.好吧,我们已经从战略上做到了藐视它,现在就要战术上重视它,如同要解决纸老虎,就要一个牙齿一个牙齿地敲,一个爪子一个爪子地拔:解决这种抽象概念也一样,先要把它具体化,细分化,然后一个一个地来. 我一般遇到新的概念都会问三个问题: 1.这个东西有什么用?用来干什么的?它的意义在哪里?(显然,如果是没用的东西,就没必

  • Java 多线程优先级实例详解

    Java 多线程优先级实例详解

    Java 多线程优先级实例详解 线程的优先级将该线程的重要性传递给调度器.尽管CPU处理现有线程集的顺序是不确定的,但是调度器将倾向于让优先权最高的线程先执行. 你可以用getPriority()来读取现有线程的优先级,并且在任何时刻都可以通过setPriority()来修改优先级. import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; public class SimplePrio

  • java LinkedList的实例详解

    java LinkedList的实例详解 站在Java的角度看,玩队列不就是玩对象引用对象嘛! 实例代码: public class LinkedList<E> implements List<E>, Deque<E> { Node<E> first; Node<E> last; int size; public boolean add(E e) { final Node<E> l = last; final Node<E>

  • Java 反射机制实例详解

    Java 反射机制实例详解 一.JAVA是动态语言吗? 一般而言,说到动态言,都是指在程序运行时允许改变程序结构或者变量类型,从这个观点看,Java和C++一样,都不是动态语言. 但JAVA它却有着一个非常突出的动态相关机制:反射.通过反射,Java可以于运行时加载.探知和使用编译期间完全求和的类.生成其对象实体,调用其方法或者对属性设值.所以Java算是一个半动态的语言吧. 反射的概念: 在Java中的反射机制是指在运行状态中,对于任意一个类,都能够知道这个类的所有属性和方法; 对于任意一个对

  • java回调机制实例详解

    java回调机制实例详解 以前不理解什么叫回调,天天听人家说加一个回调方法啥的,心里想我草,什么叫回调方法啊?然后自己就在网上找啊找啊找,找了很多也不是很明白,现在知道了,所谓回调:就是A类中调用B类中的某个方法C,然后B类中反过来调用A类中的方法D,D这个方法就叫回调方法,这样子说你是不是有点晕晕的,其实我刚开始也是这样不理解,看了人家说比较经典的回调方式: Class A实现接口CallBack callback--背景1 class A中包含一个class B的引用b --背景2 clas

  • Java 比较字符串实例详解

     Java 比较字符串实例详解 公司让实现一个自动清除1小时内数据,SQL不熟悉,无奈之下,只能本地DB存储当前时间+小时去和当前时间进行比对.折腾好半天,突然想到Java提供了一个方法,也是进行字符串比较的,傻眼了.一起来看看吧~ CompareTo()方法简介 首先,它属于java.lang.String包下,是Java提供的一个字符串比较的方法,详情介绍如下: CompareTo()返回值: int 返回值类型分别有三种,小于0,等于0,大于0 1. 如果字符串相等返回值0: 2. 如果第

  • java 内部类的实例详解

    java 内部类的实例详解 可以将一个类的定义放在另一个类的定义内部,这就是内部类. 内部类是一个非常有用的特性但又比较难理解使用的特性(鄙人到现在都没有怎么使用过内部类,对内部类也只是略知一二). 第一次见面 内部类我们从外面看是非常容易理解的,无非就是在一个类的内部在定义一个类. public class OuterClass { private String name ; private int age; public String getName() { return name; } p

  • Json转化为Java对象的实例详解

    Json转化为Java对象的实例详解 问题:前后端数据交互时,经常会遇到Json串与Java对象转化的问题,有的Java对象中还包含了List对象等. 解决方案: 引入 json-lib包,Maven坐标如下: <dependency> <groupId>net.sf.json-lib</groupId> <artifactId>json-lib</artifactId> <version>2.4</version> &l

随机推荐