关于java:世界上最快的排序算法Timsort

36次阅读

共计 5007 个字符，预计需要花费 13 分钟才能阅读完成。

背景

Timsort 是一个混合、稳固的排序算法，简略来说就是 归并排序 和二分插入排序 算法的混合体，号称世界上最好的排序算法。Timsort 始终是 Python 的规范排序算法。Java SE 7 后增加了 Timsort API，咱们从 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(\lg n)\)。该搜索算法在大量有序数组中比拟无效。

二分插入排序

插入排序算法很简略，大体过程是从第二个元素开始，顺次向前挪动替换元素直到找到适合的地位。

插入排序最优工夫复杂度也要 \(O(n)\)，咱们能够应用二分查找来缩小插入时元素的比拟次数，将工夫复杂度降为 \(\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）间接应用二分插入算法实现排序，否则执行上面步骤：

  1. 先从数组右边开始，执行 升序运行 失去一个 子序列。
  2. 将这个 子序列 放入运行堆栈里，期待 执行合并。
  3. 查看运行堆栈里的 子序列 ，如果满足 合并条件 则执行合并。
  4. 反复第一个步骤，执行下一个 升序运行。

升序运行

升序运行 就是从数组查找一段间断递增（升序）或递加（降序）子序列的过程，如果子序列为降序则将它反转为升序，也能够将这个过程简称为 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 执行流程图

graph TB
A[开始排序] 
    A --> B{MIN_MERGE?}
    B -->|MIN_MERGE >= 32| C[归并排序]
    B -->|MIN_MERGE < 32| D[二分排序]
    D --> E[升序运行]
    E --> F[执行排序]
    C --> G11[计算 minRun]
    G11 --> G1[升序运行]
    G1 --> G2[失去子序列 run]
    G1 -->|runLen < minRun| G22[补充 run 长度]
    G22 -.-> id1
    
    G22 --> G2
    G2 -->| 放入 |Z

       Z --> | 查看 run|Z1{合并条件}
       Z1 -->| 满足 | Z2[执行合并]
       Z2 -->| 不满足 | G3
       Z1 -->| 不满足 | G3
    G3[筹备下一个升序运行]
    G3 -->| 循环 |G1
    
    id1[\ 用二分插入排序把 run 前面的元素插入到后面的 run 外面 \]
    Z[(运行堆栈)]

运行合并

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

合并条件

Timsort 为了执行均衡合并（让合并的 run 大小尽可能雷同），制订了一个合并规定，对于在栈顶的三个 run，别离用 X、Y 和 Z 示意他们的长度，其中 X 在栈顶，它们必须始终维持一下的两个规定：

$$
Z > Y + X \\
Y > X
$$

一旦有其中的一个条件不被满足，则将 Y 与 X 或 Z 中的较小者合并生成新的 run，并再次查看栈顶是否依然满足条件。如果不满足则会持续进行合并，直至栈顶的三个元素都满足这两个条件，如果只剩两个run，则满足 Y > X 即可。

如下下图例子

  • 当 Z <= Y+X，将 X+Y 合并，此时只剩下两个 run。
  • 检测 Y < X，执行合并，此时只剩下 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 中确定的地位

  • 首先在 B 中找到适合的索引区间 \((2^{k − 1}, 2^{k+1} – 1)\) 使得 x 元素在这个范畴内；
  • 而后在第一步找到的范畴内通过二分搜寻来找到对应的地位。

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

正文完
java
发表至： java
2022-07-01
 0
LeetCode-350-两个数组的交集-II-Intersection-of-Two-Arrays-II
电竞数据API接口英雄联盟lol联赛统计API调用示例代码
关于java:使用开源时序数据库-GreptimeDB-存储开源实时监控-HertzBeat-的指标度量数据
java小心机(5)| 浅谈类成员初始化顺序