Java分治归并排序算法实例详解

本文实例讲述了Java分治归并排序算法。分享给大家供大家参考,具体如下:

1、分治法

许多有用的算法在结构上是递归的:为了解决一个给定的问题,算法一次或多次递归地调用其自身以解决紧密相关的若干子问题。这些算法典型地遵循分治法的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后再合并这些子问题的解来建立原问题的解。

分治模式在每层递归时都有三个步骤:

(1)分解原问题为若干子问题,这些子问题是原问题的规模较小的实例。
(2)解决这些子问题,递归地求解各子问题。然而,若子问题的规模足够小,则直接求解。
(3)合并这些子问题的解成原问题的解。

2、归并排序算法

归并排序算法完全遵循分治模式。直观上其操作如下:

(1)分解:分解待排序的n个元素的序列成各具n/2个元素的两个子序列。
(2)解决:使用归并排序递归地排序两个子序列。
(3)合并:合并两个已排序的子序列以产生已排序的答案。

当待排序的序列长度为1时,递归“开始回升”,在这种情况下不要做任何工作,因为长度为1的每个序列都已排好序。归并排序算法的关键操作是“合并”步骤中两个已排序序列的合并。我们通过调用一个辅助过程Merge(A,p,q,r)来完成合并,其中A是一个数组,p、q和r是数组下标,满足p<=q<r。该过程假设子数组A[p,q]和A[q+1,r]都已排好序。它合并这两个子数组形成单一的已排好序的子数组并代替当前的子数组A[p,r]。

过程Merge按以下方式工作。回到我们玩扑克牌的例子,假设桌上有两堆牌面朝上的牌,每堆都已排序,最小的牌在顶上。我们希望把这两堆牌合并成单一的排好序的输出堆,牌面朝下地放在桌上。我们的基本步骤包括在牌面朝上的两堆牌的顶上两张牌中选取较小的一张,将该牌从其堆中移开(该堆的顶上将显露一张新牌)并牌面朝下地将该牌放置到输出堆。

下面是Merge的伪代码:

Merge(A,p,q,r):

tmp[1,..,r-p+1]
i = p
j = q+1
while i <= q && j <= r
  if A[i] <= A[j]
  tmp[k++] = A[i++];
  else
  tmp[k++] = A[j++];
  while i <= q
  tmp[k++] = A[i++];
  while j <= r
  tmp[k++] = A[j++];
  for k2 = 0 to tmp.length
  A[k2+p] = tmp[k2];

现在我们可以把过程Merge作为归并排序算法中的一个子程序来用。下面的过程Merge_sort(A,p,r)排序子数组A[p,r]中的元素。若p>=r,则该子数组最多有一个元素,所以已经排好序。否则,分解步骤简单地计算一个下标q,将A[p,r]分成两个子数组A[p,q]和A[q+1,r],前者包含[n/2]个元素,后者包含[n/2]个元素。

Merge_sort(A,p,r):
if p < r
   q = (p+r)/2
   Merge_sort(A,p,q)
   Merge_sort(A,q+1,r)
   Merge(A,p,q,r)

为了排序整个序列A=(A[0],A[1],...,A[n]),我们执行初始调用Merge_sort(A,0,A.length),这里再次有A.length = n。图2-4自底向上地说明了当n为2的幂时该过程的操作。算法由以下操作组成:合并只含1项的序列对形成长度为2的排好序的序列,合并长度为2的序列对形成长度为4的排好序的序列,依此下去,直到长度为n/2的两个序列被合并最终形成长度为n的排好序的序列。

3、Java代码实现

public class Merge_sort_test {
  public static void Merge(int[] A,int p,int q,int r){
    int[] tmp = new int[r-p+1];//声明一个临时数组,长度为要归并数组的长度
    int i = p;  //记住左边数组第一个元素的下标
    int j = q+1; //记住右边数组第一个元素的下标
    int k = 0;
    while(i <= q && j <= r){
      //左边数组元素和右边数组元素比较,把小的元素赋给临时数组
      if(A[i] <= A[j]){
        tmp[k++] = A[i++];
      }
      else{
        tmp[k++] = A[j++];
      }
    }
    //把左边剩余的数组元素赋给临时数组
    while(i <= q){
      tmp[k++] = A[i++];
    }
    //把右边剩余的数组元素赋给临时数组
    while(j <= r){
      tmp[k++] = A[j++];
    }
    //用临时数组元素覆盖原数组元素
    for(int k2 = 0;k2 < tmp.length;k2++){
      A[k2+p] = tmp[k2];
    }
  }
  public static void/*int[]*/ Merge_sort(int[] A,int p,int r){
    int q = (p+r)/2;
    if(p < r){
      //递归调用
      Merge_sort(A,p,q);
      Merge_sort(A,q + 1,r);
      //归并排序数据元素
      Merge(A,p,q,r);
    }
    //return A;
  }
  public static void main(String[] args) {
    //
    int[] A = {5,2,4,7,1,3,2,6};
    System.out.println("原始数据: ");
    for(int i = 0;i < A.length;i++){
      System.out.print(A[i] + " ");
    }
    System.out.println();
    Merge_sort(A,0,A.length -1);
    System.out.println("输出结果: ");
    for(int i = 0;i < A.length;i++){
      System.out.print(A[i] + " ");
    }
  }
}

PS:这里再为大家推荐一款关于排序的演示工具供大家参考:

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具:
http://tools.jb51.net/aideddesign/paixu_ys

更多关于java算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

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

(0)

相关推荐

  • java实现的各种排序算法代码示例

    折半插入排序 折半插入排序是对直接插入排序的简单改进.此处介绍的折半插入,其实就是通过不断地折半来快速确定第i个元素的 插入位置,这实际上是一种查找算法:折半查找.Java的Arrays类里的binarySearch()方法,就是折半查找的实现,用 于从指定数组中查找指定元素,前提是该数组已经处于有序状态.与直接插入排序的效果相同,只是更快了一些,因 为折半插入排序可以更快地确定第i个元素的插入位置 代码: package interview; /** * @author Administrat

  • 总结Java常用排序算法

    排序算法常用的有冒泡排序,选择排序和插入排序,下面将用Java语言实现这三种排序方式,并且介绍一种由插入排序拓展出来的希尔排序. 1.冒泡排序(BubbleSort)是一种最简单的排序算法.它的基本思想是迭代地对输入序列的第一个元素到最后一个元素进行俩俩比较,当满足条件时交换这俩个元素的位置,该过程持续到不需要执行上述过程的条件时. 2.我们自定义一个排序的函数为sorter(int[]array); private static void sorter(int[] array) for(int

  • Java排序算法之堆排思想及代码实现

    在介绍堆排序前,我们需要了解一下一种数据结构 -- 顶堆. 什么是顶堆? 它是一颗完全二叉树,顶堆有大顶堆和小顶堆两种.所谓大顶堆就是在这颗完全二叉树中,任何一颗子树都满足:父结点的值 > 孩子结点的值:小顶堆则相反. 如图: 什么是堆排序(Heapsort)? 利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种.可以利用数组的特点快速定位指定索引的元素. 现在给我们一个无序数组,我们将其从小到大排序,使用堆排序的实现步骤和思想如下: 1.让这个数组变成一个大根堆 2.将最后一

  • Java语言字典序排序算法解析及代码示例

    字典序法就是按照字典排序的思想逐一产生所有排列. 在数学中,字典或词典顺序(也称为词汇顺序,字典顺序,字母顺序或词典顺序)是基于字母顺序排列的单词按字母顺序排列的方法. 这种泛化主要在于定义有序完全有序集合(通常称为字母表)的元素的序列(通常称为计算机科学中的单词)的总顺序. 对于数字1.2.3......n的排列,不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的.例如对于5个数字的排列 12354和12345,排列12345在前,排列12354在后.按照这样的规定,5个数字的所有的

  • Java基于分治法实现的快速排序算法示例

    本文实例讲述了Java基于分治法实现的快速排序算法.分享给大家供大家参考,具体如下: package cn.nwsuaf.quick; /** * 随机产生20个数,并对其进行快速排序 * * @author 刘永浪 * */ public class Quick { /** * 交换函数,实现数组中两个数的交换操作 * * @param array * 待操作数组 * @param i * 交换数组的第一个下标 * @param j * 交换数组的第二个下标 */ public static

  • 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数组常用排序算法.分享给大家供大家参考,具体如下: 1.冒泡排序法 SortArray_01.java public class SortArray_01 { public static void main(String args[]) { int[] array = { 14, 5, 86, 4, 12, 3, 21, 13, 11, 2, 55, 66, 22 }; // 创建一个初始化的一维数组array System.out.println("未排序的数组:&quo

  • 快速排序算法在Java中的实现

    快速排序的原理:选择一个关键值作为基准值.比基准值小的都在左边序列(一般是无序的),比基准值大的都在右边(一般是无序的).一般选择序列的第一个元素. 一次循环:从后往前比较,用基准值和最后一个值比较,如果比基准值小的交换位置,如果没有继续比较下一个,直到找到第一个比基准值小的值才交换.找到这个值之后,又从前往后开始比较,如果有比基准值大的,交换位置,如果没有继续比较下一个,直到找到第一个比基准值大的值才交换.直到从前往后的比较索引>从后往前比较的索引,结束第一次循环,此时,对于基准值来说,左右两

  • Java分治归并排序算法实例详解

    本文实例讲述了Java分治归并排序算法.分享给大家供大家参考,具体如下: 1.分治法 许多有用的算法在结构上是递归的:为了解决一个给定的问题,算法一次或多次递归地调用其自身以解决紧密相关的若干子问题.这些算法典型地遵循分治法的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后再合并这些子问题的解来建立原问题的解. 分治模式在每层递归时都有三个步骤: (1)分解原问题为若干子问题,这些子问题是原问题的规模较小的实例. (2)解决这些子问题,递归地求解各子问题.然而,

  • Java 归并排序算法、堆排序算法实例详解

    基本思想: 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序示例: 合并方法: 设r[i-n]由两个有序子表r[i-m]和r[m+1-n]组成,两个子表长度分别为n-i +1.n-m. j=m+1:k=i:i=i; //置两个子表的起始下标及辅助数组的起始下标 若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束 //选取r[i]和r[j]较小的存入辅助数组

  • java 归并排序的实例详解

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

  • java 中模式匹配算法-KMP算法实例详解

    java 中模式匹配算法-KMP算法实例详解 朴素模式匹配算法的最大问题就是太低效了.于是三位前辈发表了一种KMP算法,其中三个字母分别是这三个人名的首字母大写. 简单的说,KMP算法的对于主串的当前位置不回溯.也就是说,如果主串某次比较时,当前下标为i,i之前的字符和子串对应的字符匹配,那么不要再像朴素算法那样将主串的下标回溯,比如主串为"abcababcabcabcabcabc",子串为"abcabx".第一次匹配的时候,主串1,2,3,4,5字符都和子串相应的

  • Java 选择排序、插入排序、希尔算法实例详解

    1.基本思想: 在要排序的一组数中,选出最小的一个数与第一个位置的数交换:然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止. 2.实例 3.算法实现 /** * 选择排序算法 * 在未排序序列中找到最小元素,存放到排序序列的起始位置 * 再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾. * 以此类推,直到所有元素均排序完毕. * @param numbers */ public static void selectSort(int[] nu

  • java 进制转换实例详解

    java 进制转换实例详解 十进制转成十六进制: Integer.toHexString(int i) 十进制转成八进制 Integer.toOctalString(int i) 十进制转成二进制 Integer.toBinaryString(int i) 十六进制转成十进制 Integer.valueOf("FFFF",16).toString() 八进制转成十进制 Integer.valueOf("876",8).toString() 二进制转十进制 Integ

  • 数据结构之归并排序的实例详解

    归并排序 基本思想         归并排序是建立在二路归并和分治法的基础上的一个高效排序算法,将已有序的子序列合并,得到完全有序的序列:即先使每个子序 列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 将待排序序列R[0...n-1]看成是n个长度为1的有序序列,将相邻的有序表成对归并,得到n/2个长度为2的有序表:将这些有序序列 再次归并,得到n/4个长度为4的有序序列:如此反复进行下去,最后得到一个长度为n的有序序列.所以呢,我们总结一下归并排序 其实就只有两步:

  • Java 反射机制的实例详解

    Java 反射机制的实例详解 前言 今天介绍下Java的反射机制,以前我们获取一个类的实例都是使用new一个实例出来.那样太low了,今天跟我一起来学习学习一种更加高大上的方式来实现. 正文 Java反射机制定义 Java反射机制是指在运行状态中,对于任意一个类,都能够知道这个类的所有属性和方法:对于任意一个对象,都能够调用它的任意一个方法和属性:这种动态获取的信息以及动态调用对象的方法的功能称为java语言的反射机制. 用一句话总结就是反射可以实现在运行时可以知道任意一个类的属性和方法. 反射

  • java 代理机制的实例详解

    java 代理机制的实例详解 前言: java代理分静态代理和动态代理,动态代理有jdk代理和cglib代理两种,在运行时生成新的子类class文件.本文主要练习下动态代理,代码用于备忘.对于代理的原理和机制,网上有很多写的很好的,就不班门弄斧了. jdk代理 实例代码 import java.lang.reflect.InvocationHandler; import java.lang.reflect.Method; import java.lang.reflect.Proxy; publi

  • Java 序列化和反序列化实例详解

    Java 序列化和反序列化实例详解 在分布式应用中,对象只有经过序列化才能在各个分布式组件之间传输,这就涉及到两个方面的技术-发送者将对象序列化,接受者将对象反序列化,下面就是一个很好的例子! 1.实体-Employee import java.io.Serializable; public class Employee implements Serializable{ /** * */ private static final long serialVersionUID = 1L; publi

随机推荐