phpksortrecursive技巧_​面试聊一聊 Java 数组默认的排序算法我懵了

Timsort 是一个稠浊、稳定的排序算法，大略来说便是归并排序和二分插入排序算法的稠浊体，号称天下上最好的排序算法。

它由 Tim Peters 在 2002 年实现，一贯是 Python 的标准排序算法。
Java 在 1.7 后增加了 Timsort API ，从Java中的 Arrays.sort 可以看出它是默认的排序算法，紧张用于非原始类型数组排序。
以是不管是进阶编程还是口试，理解 Timsort 都是比较主要。

// List sort() default void sort(Comparator<? super E> c) { Object[] a = this.toArray(); //数组排序 Arrays.sort(a, (Comparator) c); ... }// Arrays.sort 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); } } public static void sort(Object[] a) { if (LegacyMergeSort.userRequested) legacyMergeSort(a); else ComparableTimSort.sort(a, 0, a.length, null, 0, 0); }

理解 Timsort 须要先回顾下以下知识。

指数搜索，也被称为更加搜索，是一种用于在大型数组中搜索元素而创建的算法。
它是一个两步走的过程。
首先，该算法试图找到目标元素存在的范围 (L，R)，然后在这个范围内利用二叉搜索来探求目标的准确位置。
该搜索算法在大量有序数组中比较有效。

插入排序算法很大略，大体过程是从第二个元素开始，依次向前移动交流元素直到找到得当的位置。

插入排序最优韶光繁芜度也须要 O(n) ，我们可以利用二分查找来减少插入时元素的比较次数，将韶光繁芜度降为 O(log n)。
但是把稳，二分查找插入排序仍旧须要移动相同数量的元素，但是复制数组的韶光花费低于逐一互换操作。

特点：二分插入排序紧张优点是在小数据集场景下排序效率很高。

public static int[] sort(int[] arr) throws Exception { // 开始遍历第一个元素后的所有元素 for (int i = 1; i < arr.length; i++) { // 须要插入的元素 int tmp = arr[i]; // 从已排序末了一个元素开始，如果当前元素比插入元素大，就今后移动 int j = i; while (j > 0 && tmp < arr[j - 1]) { arr[j] = arr[j - 1]; j--; } // 将元素插入 if (j != i) { arr[j] = tmp; } } return arr; } public static int[] binarySort(int[] arr) throws Exception { for (int i = 1; i < arr.length; i++) { // 须要插入的元素 int tmp = arr[i]; // 通过二分查找直接找到插入位置 int j = Math.abs(Arrays.binarySearch(arr, 0, i, tmp) + 1); // 找到插入位置后，通过数组复制向后移动，腾出元素位置 System.arraycopy(arr, j, arr, j + 1, i - j); // 将元素插入 arr[j] = tmp; } return arr; }归并排序

归并排序是分而治之策略的算法，包含两个紧张的操作：分割与合并。
大体过程是，通过递归将数组不断分成两半，一贯到无法再分割（也便是数组为空或只剩一个元素），然后进行合并排序。
大略来说合并操作便是不断取两个较小的排序数组然后将它们组合成一个更大的数组。

特点：归并排序紧张为大数据集场景设计的排序算法。

public static void mergeSortRecursive(int[] arr, int[] result, int start, int end) { // 跳出递归 if (start >= end) { return; } // 待分割的数组长度 int len = end - start; int mid = (len >> 1) + start; int left = start; // 左子数组开始索引 int right = mid + 1; // 右子数组开始索引 // 递归切割左子数组，直到只有一个元素 mergeSortRecursive(arr, result, left, mid); // 递归切割右子数组，直到只有一个元素 mergeSortRecursive(arr, result, right, end); int k = start; while (left <= mid && right <= end) { result[k++] = arr[left] < arr[right] ? arr[left++] : arr[right++]; } while (left <= mid) { result[k++] = arr[left++]; } while (right <= end) { result[k++] = arr[right++]; } for (k = start; k <= end; k++) { arr[k] = result[k]; } } public static int[] merge_sort(int[] arr) { int len = arr.length; int[] result = new int[len]; mergeSortRecursive(arr, result, 0, len - 1); return arr; }Timsort 实行过程

算法大体过程是，如果数组长度小于指定阀值（MIN_MERGE）直策应用二分插入算法完成排序，否则实行下面步骤：

升序运行便是从数组查找一段连续递增（升序）或递减（降序）子序列的过程，如果子序列为降序则将它反转为升序，也可以将这个过程简称为 run。
比如数组 [2,3,6,4,9,30]，可以查找到三个子序列，[2,3,6]、[4,9]、[30]，或说3个 run。

MIN_MERGE

这是个常数值，可以大略理解为实行归并的最小阀值，如果全体数组长度小于它，就没必要实行那么繁芜的排序，直接二分插入就行了。
在 Tim Peter 的 C 实现中为 64，但实际履历中设置为 32 效果更好，以是 java 里面的值为 32。

降序反转时为担保稳定性，相同元素不会被颠倒。

minrun

在合并序列的时候，如果 run 数量即是或者略小于 2 的幂次方的时候，合并效率最高；如果略大于 2 的幂次方，效率就会显著降落。
所以为了提高合并效率，须要只管即便掌握每个 run 的长度，通过定义一个 minrun 来表示每个 run 的最小长度，如果长度太短，就用二分插入排序把 run 后面的元素插入到前面的 run 里面。

一样平常在实行排序算法之前，会先打算出这个 minrun（它是根据数据的特点来进行自我调度），minrun 会从32到64选择一个数字，因此数据的大小除以 minrun 即是或略小于 2 的幂次方。
比如长度是 65 ，那么 minrun 的值便是 33；如果长度是 165，minrun 便是 42。

看下 Java 里面的实现，如果数据长度（n） < MIN_MERGE，则返回数据长度。
如果数据长度恰好是 2 的幂次方，则返回MIN_MERGE/2也便是16，否则返回一个MIN_MERGE/2 <= k <= MIN_MERGE范围的值k，这样可以使的 n/k 靠近但严格小于 2 的幂次方。

private static int minRunLength(int n) { assert n >= 0; int r = 0; // 如果低位任何一位是1，就会变成1 while (n >= MIN_MERGE) { r |= (n & 1); n >>= 1; } return n + r; }

MIN_GALLOP

MIN_GALLOP 是为了优化合并的过程设定的一个阈值，掌握进入 GALLOP 模式中， GALLOP 模式放在后面讲。

下面是 Timsort 实行流程图

运行合并

当栈里面的 run 知足合并条件时，它就将栈里面相邻的两个run 进行合并。

Timsort 为了实行平衡合并（让合并的 run 大小尽可能相同），制订了一个合并规则，对付在栈顶的三个run，分别用X、Y 和 Z 表示他们的长度，个中 X 在栈顶，它们必须始终坚持以下下的两个规则：

Z > Y + X Y > X

一旦有个中的一个条件不被知足，则将 Y 与 X 或 Z 中的较小者合并天生新的 run，并再次检讨栈顶是否仍旧知足条件。
如果不知足则会连续进行合并，直至栈顶的三个元素都知足这两个条件，如果只剩两个run，则知足 Y > X 即可。

如下下图例子

我们看下 Java 里面的合并实现

private void mergeCollapse() { // 当存在两个以上run实行合并检讨 while (stackSize > 1) { // 表示 Y int n = stackSize - 2; // Z <= Y + X if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) { // 如果 Z < X 合并Z+Y ，否则合并X+Y if (runLen[n - 1] < runLen[n + 1]) n--; // 合并相邻的两个run，也便是runLen[n] 和 runLen[n+1] mergeAt(n); } else if (runLen[n] <= runLen[n + 1]) { // Y <= X 合并 Y+X mergeAt(n); } else { // 知足两个条件，跳出循环 break; } } }合并内存开销

原始归并排序空间繁芜度是 O(n) 也便是数据大小。
为了实现中间项，Timsort 进行了一次归并排序，韶光开销和空间开销都比 O(n) 小。

优化是为了尽可能减少数据移动，占用更少的临时内存，先找出须要移动的元素，然后将较引言列复制到临时内存，再按终极顺序排序并添补到组合序列中。

比如我们须要合并 X [1, 2, 3, 6, 10] 和 Y [4, 5, 7, 9, 12, 14, 17]，X 中最大元素是10，我们可以通过二分查找确定，它须要插入到 Y 的第 5个位置才能担保顺序，而 Y 中最小元素是4，它须要插入到 X 中的第4个位置才能担保顺序，那么就知道了[1, 2, 3] 和 [12, 14, 17] 不须要移动，我们只须要移动 [6, 10] 和 [4, 5, 7, 9]，然后只须要分配一个大小为 2 临时存储就可以了。

在归并排序算法中合并两个数组须要逐一比较每个元素，为了优化合并的过程，设定了一个阈值 MIN_GALLOP，当B中元素向A合并时，如果A中连续 MIN_GALLOP 个元素比B中某一个元素要小，那么就进入GALLOP模式。

根据基准测试，比如当A中连续7个以上元素比B中某一元素小时切入该模式效果才好，以是初始值为7。

当进入GALLOP模式后，搜索算法变为指数搜索，分为两个步骤，比如想确定 A 中元素x在 B 中确定的位置

只有当一次运行的初始元素不是另一次运行的前七个元素之一时，驰骋才是有益的。
这意味着初始阈值为 7。