Where did I see it Collections.sort And Arrays.sort They use different sorting methods , But I can't remember when I asked , Only the interviewer wrote Timsort
There's an extra one in the back “ nothing ” word , I want to use an algorithm . Now have a look at the source code , find Collections The bottom layer actually uses Arrays Of sort Method , Instantly doubted the identity of his knowledge system .
Collections.sort The method is as follows , So it calls directly List Method of interface
@SuppressWarnings("unchecked") public static <T extends Comparable<? super
T>> void sort(List<T> list) { list.sort(null); }
Go in a little bit more , Found calling List One of the interfaces default Method
@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); } }
From this method, we can see that list Turn the set into an array and give it to Arrays Sort , After that, replace the elements of the set one by one
See Arrays.sort The source code shows that there is a TimSort Wording , That's what the interviewer thought
This is jdk7 Source code of
public static void sort(Object[] a) { if (LegacyMergeSort.userRequested)
legacyMergeSort(a); else ComparableTimSort.sort(a); }
This is jdk8 Source code of
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); } }

You can see from it 7 Follow 8 Code of , Since the code has changed, it must be the official optimization , Let's start with 7 treat with respect , There is a branch judgment in the method ,LegacyMergeSort.userRequested It means roughly “ Traditional merging and sorting of user requests ”, This branch calls the jdk1.5 The same way to implement the function , The default value is false, That is to say, it will still call ComparableTimSort.sort Method .

ComparableTimSort And TimSort The biggest difference is that the former does not use a custom comparer , The latter needs to pass in a comparator , Except this code is almost the same , They all adopt the idea of mixed sorting , Different sorting strategies will be adopted according to the data source .
jdk8 Medium when Arrays.sort Method passed in empty comparer called directly sort Method ,
public static void sort(Object[] a) { if (LegacyMergeSort.userRequested)
legacyMergeSort(a); else ComparableTimSort.sort(a, 0, a.length, null, 0, 0); }
It can be seen that by default jdk No merge sort , And officials have made it clear that they may abandon it in the future legacyMergeSort Method .

So eventually jdk It's still used TimSort sort ,ComparableTimSort And TimSort It's just the difference between including a custom comparer or not , The algorithm is exactly the same , Again, no clear distinction .
TimSort algorithm :
Timsort It's a combination of merge and sort (merge sort) And insert sort (insertion sort) And the resulting sorting algorithm , It's very efficient in reality .Tim
Peters stay 2002 The algorithm was designed in Python Used in (TimSort yes Python in list.sort
Default implementation of ). The algorithm finds the ordered blocks in the data - partition , Each partition is called a run, Then merge these by rules run.Pyhton Since 2.3 Has been used since Timsort Algorithmic sorting ,JDK
1.7 Start with Timsort Algorithm sorting array .
Timsort Main steps :

Array length less than 32 Binary insertion sorting , Otherwise, fast exhaust is adopted
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; // Length less than 2 Means there's no need for sorting , Just go back 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 ==

©2019-2020 Toolsou All rights reserved,
JAVA Detailed explanation of anomalies MySQL An interview is a must ! How to use it quickly html and css Write static page R Language cluster analysis case Dialogue between apple and Nissan suspended ,Apple Car How's it going ?java Realize the function of grabbing red packets SpringBoot practice ( five ):mybatis-plus In BaseMapper,Iservice and ServiceImpl Google says home office affects work efficiency !2021 Return to offline office in 2010 about keras use fit_generator Encountered in StopIteration Programmer Tanabata Valentine's Day confession code