Java实现世界上最快的排序算法Timsort的示例代码

目录
  • 背景
  • 前置知识
    • 指数搜索
    • 二分插入排序
    • 归并排序
  • Timsort 执行过程
    • 升序运行
    • 几个关键阀值
  • 运行合并
    • 合并条件
    • 合并内存开销
    • 合并优化

背景

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(lgn)。该搜索算法在大量有序数组中比较有效。

二分插入排序

插入排序算法很简单,大体过程是从第二个元素开始,依次向前移动交换元素直到找到合适的位置。

插入排序最优时间复杂度也要O(n) ,我们可以使用二分查找来减少插入时元素的比较次数,将时间复杂度降为logn。但是注意,二分查找插入排序仍然需要移动相同数量的元素,但是复制数组的时间消耗低于逐一互换操作。

特点:二分插入排序主要优点是在小数据集场景下排序效率很高。

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 在栈顶,它们必须始终维持一下的两个规则:

一旦有其中的一个条件不被满足,则将 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 中找到合适的索引区间(2k−1,2k+1−1) 使得 x 元素在这个范围内;
  • 然后在第一步找到的范围内通过二分搜索来找到对应的位置。

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

以上就是Java实现世界上最快的排序算法Timsort的示例代码的详细内容,更多关于Java 排序算法Timsort的资料请关注我们其它相关文章!

(0)

相关推荐

  • Java 超详细讲解十大排序算法面试无忧

    目录 排序算法的稳定性: 一.选择排序 二.冒泡排序 三.插入排序 四.希尔排序 五.堆排序 六.归并排序 七.快速排序 八.鸽巢排序 九.计数排序 十.基数排序 排序算法的稳定性: 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,如果排序以后,保证这些记录的相对次序保持不变,即在原序列中,a[i]=a[j],且 a[i] 在 a[j] 之前,排序后保证 a[i] 仍在 a[j] 之前,则称这种排序算法是稳定的:否则称为不稳定的. 一.选择排序 每次从待排序的元素中选择最小的元素,依次

  • 深入探究TimSort对归并排序算法的优化及Java实现

    简介 MergeSort对已经反向排好序的输入时复杂度为O(n^2),而timsort就是针对这种情况,对MergeSort进行优化而产生的,平均复杂度为n*O(log n),最好的情况为O(n),最坏情况n*O(log n).并且TimSort是一种稳定性排序.思想是先对待排序列进行分区,然后再对分区进行合并,看起来和MergeSort步骤一样,但是其中有一些针对反向和大规模数据的优化处理. 归并排序的优化思想 归并排序有以下几点优化方法: 和快速排序一样,对于小数组可以使用插入排序或者选择排

  • java中几种常见的排序算法总结

    目录 本节目标: [插入排序] [优化版] [希尔排序] [选择排序] [堆排序]  [冒泡排序] 介绍一个冒泡排序的优化方法:  [快速排序] [归并排序] [正文] [代码简介:]  [排序总结] 本节目标: :分析常见的比较排序算法基本原理及实现 :分析排序算法的性能分析 :分析Java中常用排序方法 1 排序 排序,就是使一串记录,按照其中某个或某些关键字的大小,递增或递减排列的操作. 平时的上下文中,提到排序 通常指排升序. 2 稳定性 两个相同的数据,如果经过排序后,排序算法能保证其

  • Java十大经典排序算法的实现图解

    目录 前言 一.排序算法 1.排序算法概述(百度百科) 2.<数据结构与算法>中的排序算法 3.算法分析 二.十大经典排序算法(Java开发版) 1.冒泡排序 2.快速排序 3.基数排序 4.插入排序 5.选择排序 6.希尔排序 7.归并排序 8.计数排序 9.堆排序 10.桶排序 前言 本文章主要是讲解我个人在学习Java开发环境的排序算法时做的一些准备,以及个人的心得体会,汇集成本篇文章,作为自己对排序算法理解的总结与笔记. 内容主要是关于十大经典排序算法的简介.原理.动静态图解和源码实现

  • Java常用的八种排序算法与代码实现

    目录 1.直接插入排序 2.希尔排序 3.简单选择排序 4.堆排序 5.冒泡排序 6.快速排序 7.归并排序 8.基数排序 1.直接插入排序 经常碰到这样一类排序问题:把新的数据插入到已经排好的数据列中. 将第一个数和第二个数排序,然后构成一个有序序列 将第三个数插入进去,构成一个新的有序序列. 对第四个数.第五个数--直到最后一个数,重复第二步. 如何写写成代码: 首先设定插入次数,即循环次数,for(int i=1;i<length;i++),1个数的那次不用插入. 设定插入数和得到已经排好

  • Java十大经典排序算法图解

    目录 0.算法概述 0.1 算法分类 0.2 算法复杂度 0.3 相关概念 1.冒泡排序(Bubble Sort) 1.1 算法描述 1.2 动图演示 1.3 代码实现 2.选择排序(Selection Sort) 2.1 算法描述 2.2 动图演示 2.3 代码实现 2.4 算法分析 3.插入排序(Insertion Sort) 3.1 算法描述 3.2 动图演示 3.3代码实现 3.4 算法分析 4.希尔排序(Shell Sort) 4.1 算法描述 4.2 动图演示 4.3 代码实现 4.

  • Java实现世界上最快的排序算法Timsort的示例代码

    目录 背景 前置知识 指数搜索 二分插入排序 归并排序 Timsort 执行过程 升序运行 几个关键阀值 运行合并 合并条件 合并内存开销 合并优化 背景 Timsort 是一个混合.稳定的排序算法,简单来说就是归并排序和二分插入排序算法的混合体,号称世界上最好的排序算法.Timsort一直是 Python 的标准排序算法.Java SE 7 后添加了Timsort API ,我们从Arrays.sort可以看出它已经是非原始类型数组的默认排序算法了.所以不管是进阶编程学习还是面试,理解 Tim

  • java实现的各种排序算法代码示例

    折半插入排序 折半插入排序是对直接插入排序的简单改进.此处介绍的折半插入,其实就是通过不断地折半来快速确定第i个元素的 插入位置,这实际上是一种查找算法:折半查找.Java的Arrays类里的binarySearch()方法,就是折半查找的实现,用 于从指定数组中查找指定元素,前提是该数组已经处于有序状态.与直接插入排序的效果相同,只是更快了一些,因 为折半插入排序可以更快地确定第i个元素的插入位置 代码: package interview; /** * @author Administrat

  • Java实现的各种排序算法(插入排序、选择排序算法、冒泡排序算法)

    一.插入排序算法实现java版本 public static int[] insert_sort(int[] a) { for (int i = 0; i < a.length; i++) { for(int j=i+1;j>0&&j<a.length;j--) { if(a[j]<a[j-1]) { int tmp = a[j]; //这样定义初始化逻辑上是可以的,j变量,每次tmp的值变化的 a[j] = a[j-1]; a[j-1] = tmp; } } }

  • Java实现8种排序算法的示例代码

    冒泡排序 O(n2) 两个数比较大小,较大的数下沉,较小的数冒起来. public static void bubbleSort(int[] a) { //临时变量 int temp; //i是循环次数,也是冒泡的结果位置下标,5个数组循环5次 for (int i = 0; i < a.length; i++) { //从最后向前面两两对比,j是比较中下标大的值 for (int j = a.length - 1; j > i; j--) { //让小的数字排在前面 if (a[j] <

  • Java基础之八大排序算法

    前言 关系 复杂度 一.直接插入排序 基本思想: 将新的数据插入已经排好的数据列中. 将第一个和第二个数排序,构成有序数列 然后将第三个数插进去,构成新的有序数列,后面的数重复这个步骤 算法描述 1.设定插入的次数,即是循环次数,for(int i=1;i<length;i++),1个数的那次不用插入. 2.设定插入的数和得到的已经排好的序列的最后一个数,insertNum和j=i-1. 3.从最后一个数向前开始循环,如果插入数小于当前数就将当前数向前移动一位 4.将当前位置放置到空的位置,即j

  • Java中七种排序算法总结分析

    目录 前言:对文章出现的一些名词进行解释 一.插入排序 1.基本思想 2.直接插入排序 3.希尔排序(缩小增量排序) 二.选择排序 1.基本思想 2.直接选择排序 3.堆排序 三.交换排序 1.基本思想 2.冒泡排序 3.快速排序(递归与非递归) 1.Hoare版 2.挖坑法 3.前后标记法(难理解) 4.快速排序优化 5.快速排序非递归 6.相关特性总结 四.归并排序(递归与非递归) 前言:对文章出现的一些名词进行解释 排序: 使一串记录,按照其中的某个或某些关键字的大小,递增或者递减排列起来

  • Java数据结构之常见排序算法(上)

    目录 认识排序 常见排序的分类 直接插入排序 希尔排序(缩小增量排序) 选择排序 堆排序 认识排序 在学校中,如果我们要参加运动会,或者军训的时候,会按照身高从矮到高进行站队,比如上课老师手上拿的考勤表,通常是按照学号从低到高进行排序的.再比如编程语言排行榜,也是在排序. 生活中有相当多的排序场景,由此可知,排序还是很重要的, 本章就会介绍常见的一些排序算法. 所谓排序呢,就拿我们上面的举例来说,会按照某个或某些关键字的大小,递增或者递减排列起来的操作,这就是排序,这里面也涉及到排序的稳定性,举

  • Java实现常见的排序算法的示例代码

    目录 一.优化后的冒泡排序 二.选择排序 三.插入排序 四.希尔排序 五.快速排序 六.随机化快速排序 七.归并排序 八.可处理负数的基数排序 一.优化后的冒泡排序 package com.yzh.sort; /* 冒泡排序 */ @SuppressWarnings({"all"}) public class BubbleSort { public static void BubbleSort(int[]a){ for (int i = 0; i <a.length-1 ; i+

  • Java实现快速排序算法可视化的示例代码

    实现效果 示例代码 import java.awt.*; public class AlgoVisualizer { private static int DELAY = 100; private SelectionSortData data; private AlgoFrame frame; public AlgoVisualizer(int sceneWidth, int sceneHeight, int N){ data = new SelectionSortData(N, sceneHe

  • Java实现插入排序算法可视化的示例代码

    参考文章 图解Java中插入排序算法的原理与实现 实现效果 示例代码 import java.awt.*; public class AlgoVisualizer { private static int DELAY = 40; private InsertionSortData data; private AlgoFrame frame; public AlgoVisualizer(int sceneWidth, int sceneHeight, int N){ // 初始化数据 data =

随机推荐