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

本文实例讲述了java数据结构排序算法之归并排序。分享给大家供大家参考,具体如下:

在前面说的那几种排序都是将一组记录按关键字大小排成一个有序的序列,而归并排序的思想是:基于合并,将两个或两个以上有序表合并成一个新的有序表

归并排序算法:假设初始序列含有n个记录,首先将这n个记录看成n个有序的子序列,每个子序列长度为1,然后两两归并,得到n/2个长度为2(n为奇数的时候,最后一个序列的长度为1)的有序子序列。在此基础上,再对长度为2的有序子序列进行亮亮归并,得到若干个长度为4的有序子序列。如此重复,直到得到一个长度为n的有序序列为止。这种方法被称作是:2-路归并排序(基本操作是将待排序列中相邻的两个有序子序列合并成一个有序序列)。

算法实现代码如下:

package exp_sort;
public class MergeSort {
  /**
   * 相邻两个有序子序列的合并算法
   *
   * @param src_array
   * @param low
   * @param high
   * @param des_array
   */
  public static void Merge(int src_array[], int low, int high,
      int des_array[]) {
    int mid;
    int i, j, k;
    mid = (low + high) / 2;
    i = low;
    k = 0;
    j = mid + 1;
    // compare two list
    while (i <= mid && j <= high) {
      if (src_array[i] <= src_array[j]) {
        des_array[k] = src_array[i];
        i = i + 1;
      } else {
        des_array[k] = src_array[j];
        j = j + 1;
      }
      k = k + 1;
    }
    // if 1 have,cat
    while (i <= mid) {
      des_array[k] = src_array[i];
      k = k + 1;
      i = i + 1;
    }
    while (j <= high) {
      des_array[k] = src_array[j];
      k = k + 1;
      j = j + 1;
    }
    for (i = 0; i < k; i++) {
      src_array[low + i] = des_array[i];
    }
  }
  /**
   * 2-路归并排序算法,递归实现
   *
   * @param src_array
   * @param low
   * @param high
   * @param des_array
   */
  public static void mergeSort(int src_array[], int low, int high,
      int des_array[]) {
    int mid;
    if (low < high) {
      mid = (low + high) / 2;
      mergeSort(src_array, low, mid, des_array);
      mergeSort(src_array, mid + 1, high, des_array);
      Merge(src_array, low, high, des_array);
    }
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array1[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    int array2[] = new int[array1.length];
    mergeSort(array1, 0, array1.length - 1, array2);
    System.out.println("\n----------after sort-------------");
    for (int ii = 0; ii < array1.length; ii++) {
      System.out.print(array1[ii] + " ");
    }
    System.out.println("\n");
  }
}

代码解释:

归并排序中一趟归并要多次调用到2-路归并算法,一趟的归并的时间复杂度是O(n),合并两个已经排好序的表的时间显然是线性的,因为最多进行了n-1次比较,其中n是元素的总数。如果有多个数,即n不为1时,递归的将前半部分数据和后半部分数据各自归并排序,得到排序后的两部分数据,再合并到一起。

算法分析:

该算法是建立在归并操作(也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作)上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,它将问题分成一些小的问题然后递归求解,而治的阶段则是将分的阶段解得的各个答案修补到一块;分治是递归非常有力的用法。注意:与快速·排序和堆排序比较,归并排序最大的特点就是,它一种稳定的排序方法。速度仅次于快速排序,一般用于对总体无序,但是各子项相对有序的数列。

复杂度:

时间复杂度为:O(nlogn) ——该算法最好、最坏和平均的时间性能。
空间复杂度为 :O(n)
比较操作的次数介于(nlogn) / 2和 nlogn - n + 1之间。
赋值操作的次数是(2nlogn)。归并算法的空间复杂度为:0 (n)
很难用于主存排序(归并排序比较占用内存,主要问题在于合并两个排序的表需要线性附加内存,在整个算法中还要花费将数据拷贝到临时数组再拷贝回来这样的一些附加操作,其结果严重放慢了排序的速度)但是效率很高,主要用于外部排序,对于重要的内部排序应用而言,一般还是选择快速排序。

归并操作的步骤如下:

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

归并排序的步骤如下(假设序列共有n个元素):

将序列每相邻两个数字进行归并操作(merge),形成floor(n/2)个序列,排序后每个序列包含两个元素
将上述序列再次归并,形成floor(n/4)个序列,每个序列包含四个元素
重复步骤2,直到所有元素排序完毕

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

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

时间: 2017-05-28

Java编程用两个栈实现队列代码分享

题目:用两个栈来实现一个队列,完成队列的Push和Pop操作. 队列中的元素为int类型. 经典题,不多说,直接上代码 import java.util.Stack; public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { st

Java实现双色球抽奖随机算法示例

第一次写技术博客,写一下以前写的一个双色球抽奖随机算法. 原理如下: 1首先初始化一个待抽奖的数组nums,数组的长度k 2. 随机一个1-k之间的随机数,得到nums[k],这样得到第一个抽奖号,nums中剔除该号码,k--. 3. 重复步骤2,直到得到全部中奖号码 class myLuck { private int mTarget; List<Integer> mNums = new ArrayList<Integer>(); //摇奖池 ///从多少个数中产生多少个数 //

java实现的RC4加密解密算法示例

本文实例讲述了java实现的RC4加密解密算法.分享给大家供大家参考,具体如下: 有一个项目,需要解析一个用户提供的rc4加密后的文件,特意搜索整理了一个Java 版本的RC4加解密算法. public static String HloveyRC4(String aInput,String aKey) { int[] iS = new int[256]; byte[] iK = new byte[256]; for (int i=0;i<256;i++) iS[i]=i; int j = 1;

Java实现合并两个有序序列算法示例

本文实例讲述了Java实现合并两个有序序列算法.分享给大家供大家参考,具体如下: 问题描述 输入:序列A<a0,a1,a2,...aq,aq+1,aq+2,...,ar>,其中a0<a1<...<aq,aq+1<aq+2<...<ar 输出:序列B<b0,b1,...,br>,其中b0<b1<...<br 算法思想 创建一个长度为r的数组R,将A中的序列看作是两个有序序列 B=A<a0,a1,a2,...,aq> C

Java使用分治算法实现排序数索引功能示例【二分搜索】

本文实例讲述了Java使用分治算法实现排序数索引功能.分享给大家供大家参考,具体如下: /** * Find the first q and return the index * First method is brutal force * Second may * be Divid and Conquer * * @author open201 * */ public class Ono { /** * f(n) = s.length = n; * * @param s * @param q

Java基于分治算法实现的线性时间选择操作示例

本文实例讲述了Java基于分治算法实现的线性时间选择操作.分享给大家供大家参考,具体如下: 线性时间选择问题:给定线性序集中n个元素和一个整数k,1≤k≤n,要求找出这n个元素中第k小的元素,(这里给定的线性集是无序的). 随机划分线性选择 线性时间选择随机划分法可以模仿随机化快速排序算法设计.基本思想是对输入数组进行递归划分,与快速排序不同的是,它只对划分出的子数组之一进行递归处理. 程序解释:利用随机函数产生划分基准,将数组a[p:r]划分成两个子数组a[p:i]和a[i+1:r],使a[p

Java基于分治算法实现的棋盘覆盖问题示例

本文实例讲述了Java基于分治算法实现的棋盘覆盖问题.分享给大家供大家参考,具体如下: 在一个2^k * 2^k个方格组成的棋盘中,有一个方格与其它的不同,若使用以下四种L型骨牌覆盖除这个特殊方格的其它方格,如何覆盖.四个L型骨牌如下图: 棋盘中的特殊方格如图: 实现的基本原理是将2^k * 2^k的棋盘分成四块2^(k - 1) * 2^(k - 1)的子棋盘,特殊方格一定在其中的一个子棋盘中,如果特殊方格在某一个子棋盘中,继续递归处理这个子棋盘,直到这个子棋盘中只有一个方格为止如果特殊方格不

Java编程实现游戏中的简单碰撞检测功能示例

本文实例讲述了Java编程中的简单碰撞检测功能.分享给大家供大家参考,具体如下: 今天在家正在写一个坦克大战的小游戏来玩,遇到了一个简单的圆和圆的碰撞检测的小问题, 碰撞检测的过程处理主要有以下三步: 1.碰撞检测(Collision Detection):返回两个或多个物体是否发生碰撞的布尔判断. 2.碰撞确定(Collision Determination):找到物体之间实际相交位置. 3.碰撞响应(Collision Response):针对两个物体之间的碰撞决定采取何种操作. 下面是关于

java实现从方法返回多个值功能示例

本文实例讲述了java实现从方法返回多个值功能.分享给大家供大家参考,具体如下: 这里介绍三个方法,使java方法返回多个值. 方法1:使用集合类 方法2:使用封装对象 方法3:使用引用传递 示例代码如下: import java.util.HashMap; import java.util.Map; public class Test { /** * 方法1:使用集合类 (Map以外的集合类也可以随意使用) * 目标:返回一个数组的最大值和最小值 */ public Map<String, I

java实现简单的英文文本单词翻译器功能示例

本文实例讲述了java实现简单的英文文本单词翻译器功能.分享给大家供大家参考,具体如下: 直接上代码: package fanyi; import java.io.BufferedReader; import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.IOException; import java.io.InputStreamReader;

Java实现对一行英文进行单词提取功能示例

本文实例讲述了Java实现对一行英文进行单词提取功能.分享给大家供大家参考,具体如下: package fanyi; import java.util.Scanner; import java.util.StringTokenizer; public class text { public static void handle(String eString) { StringTokenizer st = new StringTokenizer(eString,",!' '.;"); w

Java实现的时间戳与date对象相互转换功能示例

本文实例讲述了Java实现的时间戳与date对象相互转换功能.分享给大家供大家参考,具体如下: 一.日期转换为时间戳 public long getTimestamp() throws ParseException{ Date date1 = new SimpleDateFormat("yyyy/MM/dd HH:mm:ss") .parse("2009/12/11 00:00:00"); Date date2 = new SimpleDateFormat(&quo

Java Swing实现简单的体重指数(BMI)计算器功能示例

本文实例讲述了Java Swing实现简单的体重指数(BMI)计算器功能.分享给大家供大家参考,具体如下: BMI,Body Mass Index,身体质量指数,是用体重公斤数 除以 身高米数平方得出的,是目前国际上常用的衡量人体胖瘦程度以及是否健康的一个标准. 而本文通过运用Java Swing实现了一个简单的BMI计算器.虽然现在网页上也有相应的网页应用,但是能够做出这个计算器来,还是有点成就感的,希望自己以后做出更多比这个好的应用. 最终运行效果: 功能:可以选择三个标准:中国.亚洲.WH

Java实现矩阵加减乘除及转制等运算功能示例

本文实例讲述了Java实现矩阵加减乘除及转制等运算功能.分享给大家供大家参考,具体如下: Java初学,编写矩阵预算程序,当做工具,以便以后写算法时使用. public class MatrixOperation { public static int[][] add(int[][] matrix_a, int[][] matrix_b) { int row = matrix_a.length; int col = matrix_a[0].length; int[][] result = new