java 基本算法之归并排序实例代码

java 基本算法之归并排序实例代码

原理：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，

* 即把待排序序列分为若干个子序列，每个子序列是有序的。
     * 然后再把有序子序列合并为整体有序序列。

实例代码：

public class MergeSort {

  /**
   *
   *
   *
   * @param args
   */
  public static void main(String[] args) {
    int a[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62,
        99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51 };

    sort(a, 0, a.length - 1);
    System.out.println(Arrays.toString(a));

  }

  public static void sort(int[] data, int left, int right) {
    if (left < right) {
      // 找出中间索引
      int center = (left + right) / 2;
      // 对左边数组进行递归
      sort(data, left, center);
      // 对右边数组进行递归
      sort(data, center + 1, right);
      // 合并
      merge(data, left, center, right);
    }

  }

  public static void merge(int[] data, int left, int center, int right) {
    int[] tmpArr = new int[data.length];
    int mid = center + 1;
    // third记录中间数组的索引
    int third = left;
    int tmp = left;
    while (left <= center && mid <= right) {
      // 从两个数组中取出最小的放入中间数组
      if (data[left] <= data[mid]) {
        tmpArr[third++] = data[left++];
      } else {
        tmpArr[third++] = data[mid++];
      }

    }

    // 剩余部分依次放入中间数组
    while (left <= center) {
      tmpArr[third++] = data[left++];
    }
    while (mid <= right) {
      tmpArr[third++] = data[mid++];
    }

    // 将中间数组中的内容复制回原数组
    while (tmp <= right) {
      data[tmp] = tmpArr[tmp++];
    }
    System.out.println(Arrays.toString(data));
  }

}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (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 归并排序的实例详解

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

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

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

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

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

  • C语言中数据结构之链表归并排序实例代码

    C语言中数据结构之链表归并排序实例代码

    C语言中数据结构之链表归并排序实例代码 问题 设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增排序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏. 源程序 #include <stdio.h> #include<stdlib.h> #define N1 6 /*链表La的长度*/ #define N2 6 /*链表Lb的

  • Java Chaos Game噪声游戏实例代码

    Java Chaos Game噪声游戏实例代码

    [简介] 最近一直在读<深奥的简洁>,里面有一章介绍了几种使用噪声产生分形图的方法,感觉很有意思,于是尝试使用计算机模拟了一下,效果还不错(噪声法比传统迭代法在编程上好实现一些,后来发现这类算法还不少,搜索chaosgame可以找到更多). [Sierpinski三角形的噪声产生法] 在这些噪声游戏中,Sierpinski(谢尔宾斯基)三角形的生成规则可谓是最简单的: 1.在平面上选取三个点,标记为1.2.3,作为大三角形的顶点. 2.选择其中一点,作为"当前点"(比如选择

  • Java性能优化之数据结构实例代码

    Java性能优化之数据结构实例代码

    -举例(学生排课)- 正常思路的处理方法和优化过后的处理方法: 比如说给学生排课.学生和课程是一个多对多的关系. 按照正常的逻辑 应该有一个关联表来维护 两者之间的关系. 现在,添加一个约束条件用于校验.如:张三上学期学过的课程,在排课的时候不应该再排这种课程. 所以需要出现一个约束表(即:历史成绩表). 即:学生选课表,需要学生成绩表作为约束. -方案一:正常处理方式- 当一个学生进行再次选课的时候.需要查询学生选课表看是否已经存在. 即有如下校验: //查询 学生code和课程code分别为

  • java 排序算法之归并排序

    java 排序算法之归并排序

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

  • Java实现单链表翻转实例代码

    Java实现单链表翻转实例代码

    Java实现单链表反转,递归和非递归两种形式 /** * 反转单链表 */ /** * 定义链表 * * @author 16026 * */ class Node { int val; Node next; public Node(int val) { this.val = val; } } public class ReverseList { /** * 反转链表 * * @param head * @return */ public static Node reverseList(Node

  • Java实现FTP服务器功能实例代码

    FTP(File Transfer Protocol 文件传输协议)是Internet 上用来传送文件的协议.在Internet上通过FTP 服务器可以进行文件的上传(Upload)或下载(Download).FTP是实时联机服务,在使用它之前必须是具有该服务的一个用户(用户名和口令),工作时客户端必须先登录到作为服务器一方的计算机上,用户登录后可以进行文件搜索和文件传送等有关操作,如改变当前工作目录.列文件目录.设置传输参数及传送文件等.使用FTP可以传送所有类型的文件,如文本文件.二进制可执

  • Java执行hadoop的基本操作实例代码

    Java执行hadoop的基本操作实例代码 向HDFS上传本地文件 public static void uploadInputFile(String localFile) throws IOException{ Configuration conf = new Configuration(); String hdfsPath = "hdfs://localhost:9000/"; String hdfsInput = "hdfs://localhost:9000/user/

  • java List 排序之冒泡排序实例代码

    java List 排序之冒泡排序实例代码 List排序,这里介绍两种排序: 1.Collections.sort()排序: 假如List集合中放的是Menu对象. public class Menu{ private int id; private String name; private int seq;//自定义排序字段 //构造函数.getter.setter省略....... } List<Menu> menus=new ArrayList<Menu>(); menus.

  • java中的 toString()方法实例代码

    前言: toString()方法 相信大家都用到过,一般用于以字符串的形式返回对象的相关数据. 最近项目中需要对一个ArrayList<ArrayList<Integer>> datas  形式的集合处理. 处理要求把集合数据转换成字符串形式,格式为 :子集合1数据+"#"+子集合2数据+"#"+....+子集合n数据. 举例: 集合数据 :[[1,2,3],[2,3,5]]  要求转成为 "[1,2,3]#[2,3,5]"

随机推荐