原先好像在哪里看到Collections.sort与Arrays.sort两者使用了不同的排序方法,结果面试问到却想不起来了,只见面试官写了Timsort
后面加了个“无”字,想来代笔一种算法。现在有空看看源码,发现Collections底层使用的竟然是Arrays的sort方法,瞬间对自己的知识系统标识怀疑了。
Collections.sort 方法如下,可见其直接调用了List接口的方法
@SuppressWarnings("unchecked") public static <T extends Comparable<? super
T>> void sort(List<T> list) { list.sort(null); }
再点进去,发现调用的是List接口的一个default方法
@SuppressWarnings({"unchecked", "rawtypes"}) 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); } }
从这个方法中可以看出先把list集合转成数组交给Arrays进行排序,完成后再将排好序的数组一个个替换集合元素
查看Arrays.sort源码可看出里面出现了一个TimSort字眼,应该就是当初面试官所想的了
这个是jdk7的源码
public static void sort(Object[] a) { if (LegacyMergeSort.userRequested)
legacyMergeSort(a); else ComparableTimSort.sort(a); }
这是jdk8的源码
public static <T> void sort(T[] a, Comparator<? super T> c) { if (c == null)
{ sort(a); } else { if (LegacyMergeSort.userRequested) legacyMergeSort(a, c);
else TimSort.sort(a, 0, a.length, c, null, 0, 0); } }

从中可以看出7跟8的代码有所区别,既然代码换了吗肯定是官方进行了优化,我们先从7看起,方法里面有一个分支判断,LegacyMergeSort.userRequested的意思大致是“用户请求传统归并排序”,这个分支调用的是与jdk1.5相同的方法来实现功能,默认环境下这个值是false,也就是说最终仍会调用ComparableTimSort.sort方法。

ComparableTimSort与TimSort最大区别是前者不使用自定义比较器,后者需要传入一个比较器进去,除此代码几乎完全一样,都是采用的混合排序的思想,会根据数据源的情况采用不同的排序策略。
jdk8中当Arrays.sort方法传入空比较器进去时直接调用了sort方法,
public static void sort(Object[] a) { if (LegacyMergeSort.userRequested)
legacyMergeSort(a); else ComparableTimSort.sort(a, 0, a.length, null, 0, 0); }
由此可以看出默认情况下jdk不会采用归并排序的方式,且官方也明确说明未来可能会直接抛弃legacyMergeSort方法。

因此最终jdk仍然是采用了TimSort排序,ComparableTimSort与TimSort只是是否含自定义比较器的区别,算法完全一样,再次不做明确区别。
TimSort算法:
Timsort是结合了合并排序(merge sort)和插入排序(insertion sort)而得出的排序算法,它在现实中有很好的效率。Tim
Peters在2002年设计了该算法并在Python中使用(TimSort 是 Python 中 list.sort
的默认实现)。该算法找到数据中已经排好序的块-分区,每一个分区叫一个run,然后按规则合并这些run。Pyhton自从2.3版以来一直采用Timsort算法排序,JDK
1.7开始也采用Timsort算法对数组排序。
Timsort的主要步骤:

数组长度小于32时采用二分插入排序,否则采用快排
static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int
workLen) { assert a != null && lo >= 0 && lo <= hi && hi <= a.length; int
nRemaining = hi - lo; //长度小于2意味着没有排序必要,直接返回即可 if (nRemaining < 2) return; //
Arrays of size 0 and 1 are always sorted // MIN_MERGE=32 if (nRemaining <
MIN_MERGE) { int initRunLen = countRunAndMakeAscending(a, lo, hi);
binarySort(a, lo, hi, lo + initRunLen); return; } /** * March over the array
once, left to right, finding natural runs, * extending short natural runs to
minRun elements, and merging runs * to maintain stack invariant. */
ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen); int
minRun = minRunLength(nRemaining); do { // Identify next run int runLen =
countRunAndMakeAscending(a, lo, hi); // If run is short, extend to min(minRun,
nRemaining) if (runLen < minRun) { int force = nRemaining <= minRun ?
nRemaining : minRun; binarySort(a, lo, lo + force, lo + runLen); runLen =
force; } // Push run onto pending-run stack, and maybe merge ts.pushRun(lo,
runLen); ts.mergeCollapse(); // Advance to find next run lo += runLen;
nRemaining -= runLen; } while (nRemaining != 0); // Merge all remaining runs to
complete sort assert lo == hi; ts.mergeForceCollapse(); assert ts.stackSize ==
1;

技术
©2019-2020 Toolsou All rights reserved,
年薪20万属于什么水平?答案让人扎心!连 CEO 都不香了?这些互联网大佬接连辞任一文揭秘阿里、腾讯、百度的薪资职级百度、阿里、腾讯内部岗位级别和薪资结构,附带求职建议!可怕的不是堕落,而是清楚自己在堕落用C++跟你聊聊“原型模式” (复制/拷贝构造函数)关于keras使用fit_generator中遇到StopIteration惹什么猫都别惹熊猫!「功夫熊猫」20年对人类拿下4血C语言程序设计课程设计 之《学生成绩管理系统》Unity 场景异步加载(加载界面的实现)