说说我觉得文章可能存在的一个问题,再借此问题,正好回答下思考题!
----------------------
文章中有一段话,如下:
"时间复杂度是 O(nlogn) 的排序算法不止一个,我们已经讲过的有归并排序、快速排序,后面讲堆的时候我们还会讲到堆排序。堆排序和快速排序都有比较多的应用,比如 Java 语言采用堆排序实现排序函数,C 语言使用快速排序实现排序函数。"
这里说,”Java语言采用堆排序实现排序函数“,这句话是不是错误的?
在JDK中,排序相关的主要是两个工具类:Arrays.java 和 Collections.java,具体的排序方法是sort()。这里要注意的是,Collections.java中的sort()方法是将List转为数组,然后调用Arrays.sort()方法进行排序,具体代码如下(留言中代码格式可能有点混乱,讲究看看,也可以自行参看List.sort()):
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
在Arrays类中,sort()有一系列的重载方法,罗列几个典型的Arrays.sort()方法如下:
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(long[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}
重载方法虽然多,但是从“被排序的数组所存储的内容”这个维度可以将其分为两类:
1. 存储的数据类型是基本数据类型
2. 存储的数据类型是Object
第一种情况使用的是快排,在数据量很小的时候,使用的插入排序;
第二种情况使用的是归并排序,在数据量很小的时候,使用的也是插入排序
以上两种场景所用到的排序都是「混合式的排序」,也都是为了追求极致的性能而设计的。另外,第二种排序有个专业的名称,叫:TimSort(可以自行Wikipedia)
展开
作者回复: 👍 细心,新版本的jdk估计有优化吧,可以从代码中发现:
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
legacy的实现确实是堆排序!