vlambda博客
学习文章列表

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

第一时间获取技术干货和业界资讯!

这是因为 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)。

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

推荐阅读