Java与算法之(11) - 合并排序

时间:2022-09-26 08:51:37

天下事,合久必分,分久必合。合并排序的基本思想正是先分再合。

例如对3, 1这个数列排序,首先是分,分为3和1两个数列,然后再合并并排序。合并需要额外的辅助空间,即建立一个两个数列长度之和的空数组用于存储合并结果。

合并分为三步:

1)两个数列在起始位置各分配一个"指针",对比指针位置的数字,取较小的数字存入辅助数组。数字被移出的一侧,指针右移一格,再次比较两个指针位置的数字,直到某一侧的指针移出数组以外结束。

2)把左侧数组剩余的数字按顺序移动到辅助数组中

3)把右侧数组剩余的数字按顺序移动到辅助数组中

过程如下图:

Java与算法之(11) - 合并排序

下面把两个数组的长度都增加到2,再看一下合并过程:

Java与算法之(11) - 合并排序

观察一下这个流程可以看出,这种合并排序的前提是左右两个数列本身是有序的。所以如果对4, 2,  3, 1排序,拆成4, 2和3, 1两个数列显然是不行的,需要继续拆分4, 2为4和2,然后合并为2, 4;拆分右侧为3, 1,然后合并成1, 3。最后合并2, 4和1, 3。

以4, 3, 6, 2, 7, 1, 5为例,完整的排序过程如下图:

Java与算法之(11) - 合并排序

来看代码:

  1. import java.util.Arrays;
  2. /**
  3. * 合并排序法
  4. * Created by autfish on 2016/9/20.
  5. */
  6. public class MergeSort {
  7. public static void main(String[] args) {
  8. int[] numbers = new int[] {4, 3, 6, 2, 7, 1, 5};
  9. System.out.println("排序前: " + Arrays.toString(numbers));
  10. MergeSort ms = new MergeSort();
  11. ms.sort(numbers, 0, numbers.length - 1);
  12. System.out.println("排序后: " + Arrays.toString(numbers));
  13. }
  14. public void sort(int[] numbers, int from, int to) {
  15. int middle = (from + to) / 2;
  16. if (from < to) {
  17. sort(numbers, from, middle);
  18. sort(numbers, middle + 1, to);
  19. //左侧数列最大值小于右侧数列最小值, 不需要通过合并来调整顺序
  20. if(numbers[middle] < numbers[middle + 1])
  21. return;
  22. merge(numbers, from, middle, to);
  23. }
  24. }
  25. private void merge(int[] numbers, int from, int middle, int to) {
  26. int[] temp = new int[to - from + 1];
  27. int left = from;
  28. int right = middle + 1;
  29. int i = 0;
  30. //从拆分到两边数列各剩一个数字开始合并; 当数列中有多个数字时, 一定是已经排好序的
  31. //从两边数列左侧开始依次取数对比, 挑选小的一个放入临时数组
  32. while (left <= middle && right <= to) {
  33. if (numbers[left] < numbers[right]) {
  34. temp[i++] = numbers[left++];
  35. } else {
  36. temp[i++] = numbers[right++];
  37. }
  38. }
  39. //把左边数列剩余的数移入数组
  40. while (left <= middle) {
  41. temp[i++] = numbers[left++];
  42. }
  43. //把右边数列剩余的数移入数组
  44. while (right <= to) {
  45. temp[i++] = numbers[right++];
  46. }
  47. System.arraycopy(temp, 0, numbers, from, temp.length);
  48. }
  49. }

运行:

  1. 排序前: [4, 3, 6, 2, 7, 1, 5]
  2. 排序后: [1, 2, 3, 4, 5, 6, 7]

合并排序平均情况和最坏情况的时间复杂度都是O(nlogn),因为需要额外的辅助空间,空间复杂度为O(n)。

Java与算法之(11) - 合并排序的更多相关文章

  1. 算法笔记&lowbar;014&colon;合并排序(Java)

    1 问题描述 给定一组数据,使用合并排序得到这组数据的非降序排列. 2 解决方案 2.1 合并排序原理简介 引用自百度百科: 合并排序是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Div ...

  2. Java与算法之&lpar;10&rpar; - 希尔排序

    希尔排序是插入排序的一种,是直接插入排序的改进版本. 对于上节介绍的直接插入排序法,如果数据原来就已经按要求的顺序排列,则在排序过程中不需要进行数据移动操作,即可得到有序数列.但是,如果最初的数据是按 ...

  3. c&plus;&plus;&lpar;合并排序&rpar;

    前面一篇博客提到的快速排序是排序算法中的一种经典算法.和快速排序一样,合并排序是另外一种经常使用的排序算法.那么合并排序算法有什么不同呢?关键之处就体现在这个合并上面.    合并算法的基本步骤如下所 ...

  4. java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述

    算法是在有限步骤内求解某一问题所使用的一组定义明确的规则.通俗点说,就是计算机解题的过程.在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法.前者是推理实现的算法,后者是操作实现的算法. ...

  5. 几种常见排序算法之Java实现(插入排序、希尔排序、冒泡排序、快速排序、选择排序、归并排序)

    排序(Sorting) 是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个关键字有序的序列. 稳定度(稳定性)一个排序算法是稳定的,就是当有两个相等记录的关 ...

  6. Shell排序算法和合并排序算法

    Shell排序(希尔排序)算法Shell排序严格来说基于插入排序的思想,其又称为希尔排序或者缩小增量排序. Shell排序的流程:1.将由n个元素的数组分成n/2个数字序列,第1个数据和第n/2+1个 ...

  7. java讲讲几种常见的排序算法(二)

    java讲讲几种常见的排序算法(二) 目录 java讲讲几种常见的排序算法(一) java讲讲几种常见的排序算法(二) 堆排序 思路:构建一个小顶堆,小顶堆就是棵二叉树,他的左右孩子均大于他的根节点( ...

  8. 用 Java 实现的八种常用排序算法

    八种排序算法可以按照如图分类 交换排序 所谓交换,就是序列中任意两个元素进行比较,根据比较结果来交换各自在序列中的位置,以此达到排序的目的. 1. 冒泡排序 冒泡排序是一种简单的交换排序算法,以升序排 ...

  9. 数据结构和算法 &ndash&semi; 11&period;高级排序算法(上)

      对现实中的排序问题,算法有七把利剑可以助你马道成功. 首先排序分为四种:       交换排序: 包括冒泡排序,快速排序.       选择排序: 包括直接选择排序,堆排序.       插入排序 ...

随机推荐

  1. 如何让Table中的第一列和第二列的值相乘然后赋值给第三列

    因为需求的原因所以这样做,不废话了,直接上代码,我用的GridView绑定的数据,table也一样,因为GridView通过浏览器编译后的代码就是table.下面是aspx页面的Html代码: &lt ...

  2. BZOJ 1191 超级英雄 Hero 题解

    BZOJ 1191 超级英雄 Hero 题解 Description 现在电视台有一种节目叫做超级英雄,大概的流程就是每位选手到台上回答主持人的几个问题,然后根据回答问题的多少获得不同数目的奖品或奖金 ...

  3. 算法的上帝——Donald E&period;Knuth&lpar;转&rpar;

    开始介绍前先膜拜之~ 密尔沃基市,是美国威斯康辛州最大的城市.1938年1月10日,圣诞刚过不久,密尔沃基市民像往常一样平静地生活着.咖啡店里,有人在议论着罗斯 福总统的救市新政策,有人在议论着到底该 ...

  4. Java基础 -- 字符串&lpar;格式化输出、正则表达式&rpar;

    一 字符串 1.不可变String String对象是不可变的,查看JDK文档你就会发现,String类中每一个看起来会修改String值的方法,实际上都是创建一个全新的String对象,以包含修改后 ...

  5. Win10 - MySQL 5&period;7 密码重置

    Win10 - MySQL 5.7 密码重置 所有行为均发生在系统管理员权限的 Cmd 或 Powershell 下 注意! 本行为会导致数据库重置 # 重新安装 mysql 服务 mysqld -- ...

  6. GET与POST类型接口

    工作当中经常用到这两种类型的接口,一直对它们两个的区别一知半解,并不能从原理上说出区别. GET和POST最直观的区别应该就是GET将url包含在参数当中,POST通过request body(请求主 ...

  7. 一轮冲刺(NABCD)和需求分析

    N我们的创意是为了解决我们测量人员在测量结束后要计算一些数据的问题,当我们观测角度后,有大量的角度需要计算,有时会用到角度与弧度的转换. A我们测量人员知道计算的公式,了解一些c++和c# B我们这个 ...

  8. Javaweb学习笔记——(七)——————myexlipse基本使用、jdk5&period;0新特性及反射讲解

    1.debug调试模式: *使用这种模式,调试程序(看到程序运行停止在这一行) -显示出来行号 -双击左边,出现一个圆点,表示设置了一个断点 *使用debug as方式,运行程序 -特使是否进入到调试 ...

  9. spring事物的传播行为及隔离

    关于@Transactional注解: 添加事务注解1.使用 propagation 指定事务的传播行为, 即当前的事务方法被另外一个事务方法调用时如何使用事务, 默认取值为 REQUIRED, 即使 ...

  10. java并发之线程池的使用

    背景 当系统并发的线程数量很多,并且每个线程都是执行一个时间很短的任务就结束了,这样频繁创建线程就会大大降低系统的效率,因为频繁创建线程和销毁线程需要消耗大量的系统资源. 所以需要一个办法使得线程可以 ...