Shulou(Shulou.com)06/02 Report--

This article mainly explains "how to use the sort method in Java List". The content in the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "how to use the sort method in Java List".

Let's take a look at how the sort in List is written:

@ SuppressWarnings ({"unchecked", "rawtypes"}) default void sort (Comparator c) {Object [] a = this.toArray (); Arrays.sort (a, (Comparator) c); ListIterator I = this.listIterator (); for (Object e: a) {i.next (); i.set ((E) e);}}

First of all, you need to pass in a comparator as a parameter, which is easy to understand. after all, you must set a comparison standard. Then the list is converted into an array, and then the array is sorted. After sorting, the list is changed using iterator.

Next, let's take a look at Arrays.sort:

Public static void sort (T [] a, Comparator c) {if (c = = null) {sort (a);} else {if (LegacyMergeSort.userRequested) legacyMergeSort (a, c); else TimSort.sort (a, 0, a.length, c, null, 0,0) }} public static void sort (Object [] a) {if (LegacyMergeSort.userRequested) legacyMergeSort (a); else ComparableTimSort.sort (a, 0, a.length, null, 0,0) } static final class LegacyMergeSort {private static final boolean userRequested = java.security.AccessController.doPrivileged (new sun.security.action.GetBooleanAction ("java.util.Arrays.useLegacyMergeSort"). BooleanValue ();}

As you can see, in fact, the core of sorting is TimSort,LegacyMergeSort, which roughly means that if the version is very old, use this, the new version will not use this kind of sorting.

Let's take a look at the implementation of TimSort:

Private static final int MIN_MERGE = 32; static void sort (T [] a, int lo, int hi, Comparator c, T [] work, int workBase, int workLen) {assert c! = null & & a! = null & & lo > = 0 & lo c) {assert lo

< hi; int runHi = lo + 1; if (runHi == hi) return 1; // Find end of run, and reverse range if descending if (c.compare(a[runHi++], a[lo]) < 0) { // Descending // 一开始是递减序列，就找出最长递减序列的最后一个下标 while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0) runHi++; // 逆转前面的递减序列 reverseRange(a, lo, runHi); } else { // Ascending while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) = 0) runHi++; } return runHi - lo; } c) { assert lo >

> 1; if (c.compare (pivot, a [mid])

< 0) right = mid; else left = mid + 1; } assert left == right; /* * The invariants still hold: pivot >

= all in [lo, left) and * pivot

< all in [left, start), so pivot belongs at left. Note * that if there are elements equal to pivot, left points to the * first slot after them -- that's why this sort is stable. * Slide elements over to make room for pivot. */ int n = start - left; // The number of elements to move // Switch is just an optimization for arraycopy in default case // 比pivot大的数往后移动一位 switch (n) { case 2: a[left + 2] = a[left + 1]; case 1: a[left + 1] = a[left]; break; default: System.arraycopy(a, left, a, left + 1, n); } a[left] = pivot; } } 好了，待排序数量小于32个的讲完了，现在来说说大于等于32个情况。首先，获得一个叫minRun的东西，这是个啥含义呢： int minRun = minRunLength(nRemaining); private static int minRunLength(int n) { assert n >

= 0; int r = 0; / / Becomes 1 if any 1 bits are shifted off while (n > = MIN_MERGE) {/ / what I don't understand here is why we should do a logical OR instead of assigning (n & 1) to r directly. R | = (n & 1); n > > = 1;} return n + r;}

For various bit operators, MIN_MERGE defaults to 32, and if n is less than this value, n itself is returned. Otherwise, n is moved to the right until it is less than MIN_MERGE, and an r value is recorded, where r represents the last shift of n, whether the lowest bit of n is 0 or 1. In fact, it is easier to understand the notes:

Returns the minimum acceptable run length for an array of the specified length. Natural runs shorter than this will be extended with binarySort.Roughly speaking, the computation is: If n < MIN_MERGE, return n (it's too small to bother with fancy stuff). Else if n is an exact power of 2, return MIN_MERGE/2.Else return an int k, MIN_MERGE/2

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.