Java排序算法总结之归并排序

本文实例讲述了Java排序算法总结之归并排序。分享给大家供大家参考。具体分析如下：

归并操作(merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。和快速排序类似，让我们一起来看，归并在Java中的实现。

归并排序（Merge）是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

归并排序算法稳定，数组需要O(n)的额外空间，链表需要O(log(n))的额外空间，时间复杂度为O(nlog(n))，算法不是自适应的，不需要对数据的随机读取。

工作原理：

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

代码实现：

////////////////
public void mergeSort(){
 long[] workSpace = new long[nElems];
 recMergeSort(workSpace,0,nElems-1);
}
private void recMergeSort(long[] workSpace,int lowerBound,int upperBound){
 if(lowerBound == upperBound){
  return;
 }
 else{
  int mid=(lowerBound+upperBound)/2;
  recMergeSort(workSpace, lowerBound, mid);
  recMergeSort(workSpace, mid+1, upperBound);
  merge(workSpace, lowerBound, mid+1, upperBound);
 }
}
private void merge(long[] workSpace,int lowPtr,int highPtr,int upperBound){
 int j = 0;
 int lowerBound = lowPtr;
 int mid = highPtr - 1;
 int n = upperBound-lowerBound+1;
 while(lowPtr<=mid&&highPtr<=upperBound){
  if(theArray[lowPtr]<theArray[highPtr]){
  workSpace[j++]=theArray[lowPtr++];
  }
  else{
  workSpace[j++]=theArray[highPtr++];
  }
 }
 while(lowPtr<=mid){
  workSpace[j++] = theArray[lowPtr++];
 }
 while(highPtr<=upperBound){
  workSpace[j++] = theArray[highPtr++];
 }
 for(j=0;j<n;j++){
  theArray[lowerBound+j]=workSpace[j];
 }
}

归并排序是比较稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要.这也是它比快速排序优势的地方.

希望本文所述对大家的java程序设计有所帮助。

赞 (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编程中实现归并排序算法的实例教程

    算法概述/思路 归并排序是基于一种被称为"分治"(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 基本算法之归并排序实例代码 原理:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表, * 即把待排序序列分为若干个子序列,每个子序列是有序的.      * 然后再把有序子序列合并为整体有序序列. 实例代码: public class MergeSort { /** * * * * @param args */ public static void main(String[] args) { int a[] = { 49, 38, 65, 97, 76, 13,

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

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

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

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

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

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

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

  • 浅析java 归并排序算法

    浅析java 归并排序算法

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

  • Java排序算法总结之归并排序

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

  • Java排序算法三之归并排序的递归与非递归的实现示例解析

    归并有递归和非递归两种. 归并的思想是: 1.将原数组首先进行两个元素为一组的排序,然后合并为四个一组,八个一组,直至合并整个数组: 2.合并两个子数组的时候,需要借助一个临时数组,用来存放当前的归并后的两个数组: 3.将临时数组复制回原数组对应的位置. 非递归的代码如下: package mergesort; import java.util.Arrays; import java.util.Random; import java.util.Scanner; //归并排序的非递归算法 publ

  • Java排序算法之归并排序简单实现

    算法描述:对于给定的一组记录,首先将每两个相邻的长度为1的子序列进行归并,得到 n/2(向上取整)个长度为2或1的有序子序列,再将其两两归并,反复执行此过程,直到得到一个有序序列. package sorting; /** * 归并排序 * 平均O(nlogn),最好O(nlogn),最坏O(nlogn);空间复杂度O(n);稳定;较复杂 * @author zeng * */ public class MergeSort { public static void merge(int[] a,

  • java 排序算法之归并排序

    java 排序算法之归并排序

    目录 简单介绍 基本思想 思路分析 代码实现 对代码的一些改进 大数据量耗时测试 复杂度 简单介绍 归并排序(merge sort)是利用 归并 的思想实现的排序方法,该算法采用经典的 分治(divide-and-conquer)策略 : 分(divide):将问题分成一些小的问题,然后递归求解 治(conquer):将分的阶段得到的各答案「修补」在一起 即:分而治之 该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使

  • 图解Java排序算法之归并排序

    图解Java排序算法之归并排序

    目录 基本思想 合并相邻有序子序列 代码实现 总结 基本思想 归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之). 分而治之 可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现).分阶段可以理解为就是递归拆分子序列的过程,递归深

  • Java排序算法总结之冒泡排序

    本文实例讲述了Java排序算法总结之冒泡排序.分享给大家供大家参考.具体分析如下: 前言:冒泡排序(BubbleSort)就是依次比较相邻的两个数,将小数放在前面,大数放在后面. 下面让我们一起    来看冒泡排序在Java中的算法实现. 冒泡排序是计算机的一种排序方法,它的时间复杂度为O(n^2),虽然不及堆排序.快速排序的O(nlogn,底数为2),但是有两个优点: 1."编程复杂度"很低,很容易写出代码: 2.具有稳定性,这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后

  • Java 排序算法整合（冒泡，快速，希尔，拓扑，归并）

    冒泡排序介绍 冒泡排序(Bubble Sort),又被称为气泡排序或泡沫排序. 它是一种较简单的排序算法.它会遍历若干次要排序的数列,每次遍历时,它都会从前往后依次的比较相邻两个数的大小:如果前者比后者大,则交换它们的位置.这样,一次遍历之后,最大的元素就在数列的末尾! 采用相同的方法再次遍历时,第二大的元素就被排列在最大元素之前.重复此操作,直到整个数列都有序为止! 冒泡排序图文说明 /* * a -- 待排序的数组 * n -- 数组的长度 */ public static void bub

  • 盘点几种常见的java排序算法

    盘点几种常见的java排序算法

    目录 1.插入排序 2.分治排序法,快速排序法 3.冒泡排序 low版 4.冒泡排序 bigger版 5.选择排序 6. 归并排序 8. 堆排序 9. 其他排序 10. 比较 总结 1.插入排序 这个打麻将或者打扑克的很好理解, 比如有左手有一副牌1,2,4,7 ,来一张3的牌, 是不是就是手拿着这张牌从右往左插到2,4之间 一次插入排序的操作过程: 将待插元素,依次与已排序好的子数列元素从后到前进行比较,如果当前元素值比待插元素值大,则将移位到与其相邻的后一个位置,否则直接将待插元素插入当前元

  • Java排序算法之SleepSort排序示例

    本文实例讲述了Java排序算法之SleepSort排序.分享给大家供大家参考,具体如下: 分享一个很有创意的排序算法:sleepSort .巧妙利用了线程的sleep(),代码如下: public class SleepSort { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] ints = {1,4,7,3,8,9,2,6,5}; So

  • Java排序算法总结之选择排序

    本文实例讲述了Java排序算法总结之选择排序.分享给大家供大家参考.具体分析如下: 选择排序的基本操作就是每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完.算法不稳定,O(1)的额外的空间,比较的时间复杂度为O(n^2),交换的时间复杂度为O(n),并不是自适应的.在大多数情况下都不推荐使用.只有在希望减少交换次数的情况下可以用.   基本思想   n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果: ①初始状态:

随机推荐