面试题:JDK6为啥默认排序是归并排序呢?

JAVA herman 326浏览
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:xttblog,发送下载链接帮助你免费下载!
本博客日IP超过1800,PV 2600 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:xttblog,之前的微信号好友位已满,备注:返现
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领

这是因为 Java 做为一个平台型语言,对于稳定性要求较高!归并有一个快排没有的优点,就是归并排序是稳定的。

因为合并排序比较稳定,比快排稳定,快排有可能时间复杂度达到 O(n ^ 2),但是合并排序就相对趋于 O(nlogn),但是合并排序的一个缺点就是要用到两个临时的数组内存!

很多人可能不理解什么是稳定?给你举个例子吧。[1,2,1,3] 排序过后成为 [1, 1, 2, 3]。使用快速排序后,这两个 1 可能就换了个位置。这里用单纯的数字,你可能看不出来效果。但是如果是用对象比较的话,假如两个对象的 compare 值是对等的,但是排序过后相互顺序却变了,在内存上是有意义的。

另外,快排是不是最快的排序算法。

在 JDK8 中,如果你看过源码就会知道,其实针对不同的情况使用了不同的排序算法,简单罗列下:1.如果是简单对象数据,例如int,double,且数组长度在一定阀值内,则使用快排,如果在阀值外,则用归并;如果是复杂对象数组,则如果数组长度在一定阀值以内,则使用折半插入排序,如果长度在阀值外,则使用归并法,但是如果归并二分后小于阀值了,则在内部还是会使用折半插入排序。

那么为什么复杂对象不使用快速排序呢?因为对于一个 hashcode 计算复杂的对象来说,移动的成本远低于比较的成本。

归并排序过程

归并排序在最坏情况下的键值比较次数十分接近基于比较的排序算法在理论上能够达到的最少次数。当n很大时,归并排序算法比较的次数是要小于0.25n次的,因此效率也属于θ(nlogn)。

相比于快速排序和堆排序,归并算法的一个显著优点在于其稳定性,主要缺点在于需要线性的额外空间。归并算法也可以做到原地排序,使空间复杂度降至 O(1)。

归并排序有两类主要的变化形式:

  • 算法自底向上合并数组的一个个元素对,然后再合并有些有序对,依次类推。这种方式是迭代式的,因此避免了使用堆栈处理递归调用时的空间和时间开销。
  • 算法把数组划分为待排序的多个部分,再对它们递归排序,最后将其合并在一起。这个方案尤其适合对存放在二级存储空间(内存-外存)的文件进行排序,也被称为多路归并排序(multiway mergesort)。

以上希望能够帮助大家解惑!

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加作者微信号1:xmtxtt(5000人已满),微信号2:codedq(5000人已满),微信号3:xttblog(超2800)。备注:“xttblog”,添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系!

本文原文出处:业余草: » 面试题:JDK6为啥默认排序是归并排序呢?