面试 11:玩转 Java 归并排序
面试 11:Java 玩转归并排序
前面讲了冒泡、选择、插入三种简单排序,时间复杂度都是 O(n²),今天,我们终于迎来了更高级的排序:归并排序。
虽然在这之前还有希尔排序和堆排序,但由于时间关系,我们这里就直接跳过,确实感兴趣的请直接 Google。
归并排序
我们总是可以将一个数组一分为二,然后二分为四,直到每一组只有两个元素,这可以理解为个递归的过程,然后将两个元素进行排序,之后再将两个元素为一组进行排序。直到所有的元素都排序完成。同样我们来看下边这个动图。
归并排序算法是采用分治法的一个非常典型的应用,且各层分治递归可以同时进行。
归并算法的思想
归并算法其实可以分为递归法和迭代法(自底向上归并),两种实现对于最小集合的归并操作思想是一样的。区别在于如何划分数组,我们先介绍下算法最基本的操作:
- 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
- 设定两个指针,最初位置分别为两个已经排序序列的起始位置;
- 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
- 重复步骤 3 直到某一指针到达序列尾;
- 将另一序列剩下的所有元素直接复制到合并序列尾。
我们来看看 Java 递归代码是怎么实现的:
public class Test09 { private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } private static void printArr(int[] arr) { for (int anArr : arr) { System.out.print(anArr + " "); } } private static void mergeSort(int[] arr) { if (arr == null) return; mergeSort(arr, 0, arr.length - 1); } private static void mergeSort(int[] arr, int start, int end) { if (start >= end) return; // 找出中间索引 int mid = start + (end - start >> 1); // 对左边数组进行递归 mergeSort(arr, start, mid); // 对右边数组进行递归 mergeSort(arr, mid + 1, end); // 合并 merge(arr, start, mid, end); } private static void merge(int[] arr, int start, int mid, int end) { // 先建立一个临时数组,用于存放排序后的数据 int[] tmpArr = new int[arr.length]; int start1 = start, end1 = mid, start2 = mid + 1, end2 = end; // 创建一个下标 int pos = start1; // 缓存左边数组的第一个元素的索引 int tmp = start1; while (start1 <= end1 && start2 <= end2) { // 从两个数组中取出最小的放入临时数组 if (arr[start1] <= arr[start2]) tmpArr[pos++] = arr[start1++]; else tmpArr[pos++] = arr[start2++]; } // 剩余部分依次放入临时数组,实际上下面两个 while 只会执行其中一个 while (start1 <= end1) { tmpArr[pos++] = arr[start1++]; } while (start2 <= end2) { tmpArr[pos++] = arr[start2++]; } // 将临时数组中的内容拷贝回原来的数组中 while (tmp <= end) { arr[tmp] = tmpArr[tmp++]; } } public static void main(String[] args) { int[] arr = {6, 4, 2, 1, 8, 3, 7, 9, 5}; mergeSort(arr); printArr(arr); } }
归并排序算法总的时间复杂度是 O(nlogn),而且这是归并排序算法中最好、最坏、平均的时间性能。
而由于在归并排序过程中需要与原始记录序列同样数量的存储空间存放归并结果以及递归时压入栈的数据占用的空间:n + logn,所以空间复杂度为 O(n)。
总结
归并排序虽然比较稳定,在时间上也是非常有效的,但是这种算法很消耗空间,一般来说只有在外部排序才会采用这个方法,但在内部排序不会用这种方法,而是用快速排序。明天,我们将带来排序算法中的王牌:快速排序。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
intellij idea tomcat热部署配置
1.设置Debugger-HotSwap 在setting界面,打开Debugger-HotSwap选项,确保勾选了Build project before reloading classes,同时选择Reload classes after compilation为Always。这样我们在编译某个修改了的java文件之后,就会利用HotSwap机制reload class,而Build project before reloading classes就确保了其他修改过的文件一起同步到部署目录。 2.项目设置 在Project Structure视图中,在Project setting --> Articfacts选项中,选择war:Exploded类型的modules,然后设置编译输出项目的路径 将你的构建输出目录直接设置在源程序目录中,然后重定向的docBase直接指向你的web根目录(就是WEB-INF的父目录)。这样,你只要将编译输出目录设置为WEB-INF\classes就行了,而且,修改JSP文件都不要重新构建,唯一要做的就是修改了java文件之后compile一下。...
- 下一篇
(码友推荐)2018-07-18 .NET及相关开发资讯速递
(码友推荐)2018-07-18 .NET及相关开发资讯速递: 1.如何打造一个完美的错误提示2.Docker 和 Kubernetes 从听过到略懂:给程序员的旋风教程3.Visual Studio IntelliCode now infers coding conventions for consistent code4.2018年过半,为你总结了这13个主要的设计趋势5.dotnet Framework 源代码 类库的意思6.温故之.NET进程间通信——内存映射文件7.针对 ElasticSearch .Net 客户端的一些封装8.谈谈 Git 代码回滚9.SQL解析在美团点评中是如何应用的? 围观地址[码友网]:https://codedefault.com/
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- CentOS8编译安装MySQL8.0.19
- SpringBoot2初体验,简单认识spring boot2并且搭建基础工程
- CentOS8安装Docker,最新的服务器搭配容器使用
- CentOS7,CentOS8安装Elasticsearch6.8.6
- Red5直播服务器,属于Java语言的直播服务器
- CentOS8安装MyCat,轻松搞定数据库的读写分离、垂直分库、水平分库
- Hadoop3单机部署,实现最简伪集群
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题