Arrays.sort的背后jdk干了什么

十年砍柴不误工

Arrays.sort的背后jdk干了什么Arrays.sort的大体调用逻辑大家一般在进行排序的时候都会调用到arrays.sort()方法进行排序，而排序的后面jdk为了我们做了很多事情。一般我们调用的collections.sort(Comparator c) ,list.sort(Comparator c)方法，最后都会调用到arrays.sort。 ? ?public static void sort(T[] a, Comparator c) { ? ? ? ?if (c == null) { ? ? ? ? ? ?//没有Comparator，走ComparableTimSort排序逻辑 ? ? ? ? ? ?sort(a, fromIndex, toIndex); ? ? ? ?} else { ? ? ? ? ? ?//越位，范围检查 ? ? ? ? ? ?rangeCheck(a.length, fromIndex, toIndex); ? ? ? ? ? ?//LegacyMergeSort.userRequested默认返回false ? ? ? ? ? ?//legacyMergeSort(a, fromIndex, toIndex, c)方法要被时代淘汰了 ? ? ? ? ? ?if (LegacyMergeSort.userRequested) ? ? ? ? ? ? ? ?legacyMergeSort(a, fromIndex, toIndex, c); ? ? ? ? ? ?else ? ? ? ? ? ? ? ?//主角TimSort排序 ? ? ? ? ? ? ? ?TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0); ? ? ? ?} ? ?}当规则对比器为空时调用ComparableTimSort的入口代码，ComparableTimSort是跟timsort一样原理的排序算法，只是元素的比较规则使用了一个默认对比规则。 ? ?public static void sort(Object[] a) { ? ? ? ?if (LegacyMergeSort.userRequested) ? ? ? ? ? ?legacyMergeSort(a); ? ? ? ?else ? ? ? ? ? ?ComparableTimSort.sort(a, 0, a.length, null, 0, 0); ? ?}legacyMergeSort排序的方法，方法上面就被标注了To be removed in a future release，光荣退休了。 ? ?/** To be removed in a future release. */ ? ?private static void legacyMergeSort(T[] a, int fromIndex, int toIndex, ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Comparator c) { ? ? ? ?T[] aux = copyOfRange(a, fromIndex, toIndex); ? ? ? ?if (c==null) ? ? ? ? ? ?mergeSort(aux, a, fromIndex, toIndex, -fromIndex); ? ? ? ?else ? ? ? ? ? ?mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c); ? ?}然后就是今天的主角Timsort排序。/** ? ? * Sorts the given range, using the given workspace array slice ? ? * for temp storage when possible. This method is designed to be ? ? * invoked from public methods (in class Arrays) after performing ? ? * any necessary array bounds checks and expanding parameters into ? ? * the required forms. ? ? * ? ? * @param a the array to be sorted ? ? * @param lo the index of the first element, inclusive, to be sorted ? ? * @param hi the index of the last element, exclusive, to be sorted ? ? * @param c the comparator to use ? ? * @param work a workspace array (slice) ? ? * @param workBase origin of usable space in work array ? ? * @param workLen usable size of work array ? ? * @since 1.8 ? ? */ ? ?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 ts = new TimSort(a, c, work, workBase, workLen); ? ? ? ?//计算分区最小个数，少于这个长度就需要对其进行扩展。 ? ? ? ?int minRun = minRunLength(nRemaining); ? ? ? ?do { ? ? ? ? ? ?// 找出 排序数组中 一段升序数组 的长度 ? ? ? ? ? ?int runLen = countRunAndMakeAscending(a, lo, hi, c); ? ? ? ? ? ?//如果归并分区个数小于之前计算出的minRun ? ? ? ? ? ?if (runLen = 0; int r = 0; // Becomes 1 if any 1 bits are shifted off while (n >= MIN_MERGE) { r |= (n & 1); n >>= 1; } return n + r; }minRunLength方法决定了分区的最小值。MIN_MERGE默认为32，n为排序数组的长度。如果n小于MIN_MERGE，那么返回?n?本身。否则会将?n?不断地右移，直到少于?MIN_MERGE，同时记录一个?r?值，r 代表最后一次移位n时，n最低位是0还是1。?最后返回?n + r，这也意味着只保留最高的 5 位，再加上第六位。 ? ?private static int countRunAndMakeAscending(T[] a, int lo, int hi, ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Comparator c) { ? ? ? ?assert lo = 0) ? ? ? ? ? ? ? ?runHi++; ? ? ? ?} ? ? ? ?return runHi - lo; ? ?}寻找在数组中有一致顺序的一段，如果是降序则翻转。这段具备顺序的片段为a，如果a大于等于分区最小长度则入栈等待归并；如果a小于分区最小长度，则将片段a后的区域（区域长度 = 最小分区长度 - 片段a长度），达到最小分区长度，进行分区排序。2. 分区排序 ? ?@SuppressWarnings("fallthrough") ? ?private static void binarySort(T[] a, int lo, int hi, int start, ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Comparator c) { ? ? ? ?assert lo >> 1; ? ? ? ? ? ? ? ?if (c.compare(pivot, a[mid]) 1) { ? ? ? ? ? ?int n = stackSize - 2; ? ? ? ? ? ?//当栈内元素大于3个元素 且第一个分区长度 小于等于 第2个分区长度 加 第3个分区长度 ? ? ? ? ? ?if (n > 0 & runLen[n-1] = 2; ? ? ? ?assert i >= 0; ? ? ? ?assert i == stackSize - 2 || i == stackSize - 3; ? ? ? ?int base1 = runBase[i]; ? ? ? ?int len1 = runLen[i]; ? ? ? ?int base2 = runBase[i + 1]; ? ? ? ?int len2 = runLen[i + 1]; ? ? ? ?assert len1 > 0 & len2 > 0; ? ? ? ?assert base1 + len1 == base2; ? ? ? ? ? ? ? ?//合并分区 ? ? ? ?runLen[i] = len1 + len2; ? ? ? ?//合并后移动栈中元素的位置 ? ? ? ?if (i == stackSize - 3) { ? ? ? ? ? ?runBase[i + 1] = runBase[i + 2]; ? ? ? ? ? ?runLen[i + 1] = runLen[i + 2]; ? ? ? ?} ? ? ? ?stackSize--; ? ? ? ? ? ? ? ?//用第2个分区的第一个元素 在 第1个分区 寻找 它的合适位置index ? ? ? ?//index之前是有序的，之后就是要归并 第2分区的所有元素 和 第1分区index之后的元素 ? ? ? ?int k = gallopRight(a[base2], a, base1, len1, 0, c); ? ? ? ?assert k >= 0; ? ? ? ?base1 += k; ? ? ? ?len1 -= k; ? ? ? ?if (len1 == 0) ? ? ? ? ? ?return; ? ? ? ?//与上面同理 找到run1的最后一个元素在run2中的位置。 ? ? ? ?//随后的元素在run2中可以忽略(因为它们已经就绪)。 ? ? ? ?len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1, c); ? ? ? ?assert len2 >= 0; ? ? ? ?if (len2 == 0) ? ? ? ? ? ?return; ? ? ? ?// Merge remaining runs, using tmp array with min(len1, len2) elements ? ? ? ?if (len1 runLen[i-1] + runLen[i]runLen[i-1] > runLen[i]在大多数情况下，仅检查栈顶的3个run是否满足这个约束条件是可以保证整个栈内所有run均满足该约束条件。但是在一些特殊的情况下就不行了，如下面这个栈（右侧为栈顶）：120, 80, 25, 20, 30对照上面的源码，因为25 45 + 30，45 > 30，满足约束条件，此时归并就终止了。但是注意栈里的其他run，120 b。这样可以触发“特殊情况”，即：a和b在某一次归并操作后，会同时成为“是否移动元素”的临界条件。这样，在“特殊情况”下，优化后的归并操作可能陷入死循环。解决方案解决方案其实很简单，确保compare(a,b)操作中，如果a>b，那么bb，那么bb, b>c，那么a>c。x=y时，(x op z) = ( y op z )顺带一说，在重写Java api的时候，如果没有十足把握的话，可以将它委托给另一个Java基础类（如String、Integer等）的对应api实现上。例如冯庆的解决方案，本质上就是将compare(a,b)操作委托给了int来实现。结语给大家附上作者tim peters写的python之禅。Beautiful is better than ugly.Explicit is better than implicit.Simple is better than complex.Complex is better than complicated.Flat is better than nested.Sparse is better than dense.Readability counts.Special cases aren't special enough to break the rules.Although practicality beats purity.Errors should never pass silently.Unless explicitly silenced.In the face of ambiguity, refuse the temptation to guess.There should be one— and preferably only one —obvious way to do it.Although that way may not be obvious at first unless you're Dutch.Now is better than never.Although never is often better thanrightnow.If the implementation is hard to explain, it's a bad idea.If the implementation is easy to explain, it may be a good idea.Namespaces are one honking great idea—let's do more of those!译文美丽胜于丑陋。显式胜于隐式。简单胜于复杂。复杂胜于复杂。扁平比嵌套更好。稀疏胜于密实。可读性很重要。特殊情况还不足以打破规则。尽管实用性胜过纯度。错误绝不能默默传递。除非明确地保持沉默。面对模棱两可，拒绝猜测的诱惑。应该有一种（最好只有一种）明显的方式来做到这一点。尽管除非您是荷兰人，否则一开始这种方式可能并不明显。现在总比没有好。虽然从未往往比右了。如果实现难以解释，那是个坏主意。如果实现易于解释，则可能是个好主意。命名空间是一个很棒的主意-让我们多做些吧！关注得物技术，携手走向技术的云端文｜feng逸