TimSort——最快的排序算法

TimSort——最快的排序算法

排序算法是每个程序员绕不开的课题,无论是大学课程还是日常工作,都离不开排序算法。常见的排序算法有:冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、基数排序等。下面是这些算法性能的概览:

算法平均时间复杂度最好情况最差情况空间复杂度排序方式稳定性
冒泡排序 O ( n 2 ) O(n^2) O(n2) O ( n ) O(n) O(n) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)in-place稳定
选择排序 O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)in-place不稳定
插入排序 O ( n 2 ) O(n^2) O(n2) O ( n ) O(n) O(n) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)in-place稳定
希尔排序 O ( n log ⁡ n ) O(n\log n) O(nlogn) O ( n log ⁡ n ) O(n\log n) O(nlogn) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)in-place不稳定
归并排序 O ( n log ⁡ n ) O(n\log n) O(nlogn) O ( n log ⁡ n ) O(n\log n) O(nlogn) O ( n log ⁡ n ) O(n\log n) O(nlogn) O ( n ) O(n) O(n)out-place稳定
快速排序 O ( n log ⁡ n ) O(n\log n) O(nlogn) O ( n log ⁡ n ) O(n\log n) O(nlogn) O ( n 2 ) O(n^2) O(n2) O ( n ) O(n) O(n)in-place不稳定
堆排序 O ( n log ⁡ n ) O(n\log n) O(nlogn) O ( n log ⁡ n ) O(n\log n) O(nlogn) O ( n log ⁡ n ) O(n\log n) O(nlogn) O ( 1 ) O(1) O(1)in-place不稳定
计数排序 O ( n + k ) O(n+k) O(n+k) O ( n + k ) O(n+k) O(n+k) O ( n + k ) O(n+k) O(n+k) O ( k ) O(k) O(k)out-place稳定
桶排序 O ( n + k ) O(n+k) O(n+k) O ( n + k ) O(n+k) O(n+k) O ( n 2 ) O(n^2) O(n2) O ( n ) O(n) O(n)out-place稳定
基数排序 O ( n k ) O(nk) O(nk) O ( n k ) O(nk) O(nk) O ( n k ) O(nk) O(nk) O ( n + k ) O(n+k) O(n+k)out-place稳定

上述算法中,我们日常用的最多的可能是快速排序和堆排序,这两个算法都是性能很高的排序算法,缺点是不稳定。今天要介绍的 TimSort 算法性能比快速排序和堆排序还高,且是稳定排序算法。

文章目录

    • TimSort 简介
    • TimSort 原理
    • TimSort 详解
      • 小数组用插入排序
      • Run 块
      • 归并
    • 算法实现
    • 总结

TimSort 简介

TimSort 算法是 Tim Peters (就是写 Python 之禅 的那个大神) 于 2001 年为 Python 语言创建的。该算法建立在插入排序和归并排序的基础之上,兼具插入排序和归并排序的优点。

Tim Peters

图1. Tim Peters,就是这位大神开创了 TimSort

TimSort 的平均时间复杂度为 O ( n log ⁡ n ) O(n\log n) O(nlogn) ,最好情况 O ( n ) O(n) O(n) ,最差情况 O ( n log ⁡ n ) O(n\log n) O(nlogn) 。空间复杂度 O ( n ) O(n) O(n) ,是一个稳定的排序算法。

算法平均时间复杂度最好情况最差情况空间复杂度排序方式稳定性
快速排序 O ( n log ⁡ n ) O(n\log n) O(nlogn) O ( n log ⁡ n ) O(n\log n) O(nlogn) O ( n 2 ) O(n^2) O(n2) O ( n ) O(n) O(n)in-place不稳定
堆排序 O ( n log ⁡ n ) O(n\log n) O(nlogn) O ( n log ⁡ n ) O(n\log n) O(nlogn) O ( n log ⁡ n ) O(n\log n) O(nlogn) O ( 1 ) O(1) O(1)in-place不稳定
归并排序 O ( n log ⁡ n ) O(n\log n) O(nlogn) O ( n log ⁡ n ) O(n\log n) O(nlogn) O ( n log ⁡ n ) O(n\log n) O(nlogn) O ( n ) O(n) O(n)out-place稳定
TimSort O ( n log ⁡ n ) O(n\log n) O(nlogn) O ( n ) O(n) O(n) O ( n log ⁡ n ) O(n\log n) O(nlogn) O ( n ) O(n) O(n)out-place稳定

自该算法被发明以来,已被 Python、Java、Android 平台和 GNU Octave 用作默认排序算法。Java 中的 Arrays.sort(),Python 中的 sort()sorted() 背后用的都是 TimSort。

TimSort 原理

TimSort 的排序思想并不复杂,首先使用插入排序对小块进行排序,然后使用归并排序合并这些块。

TimSort 会将数组(列表)分成名为 Run 的小块。首先使用插入排序对这些 run 块进行排序,然后使用归并排序中的 combine 函数合并这些 run 块。如果数组的大小小于 run 块的大小,则仅使用插入排序对数组进行排序。run 块的大小可能从 32 到 64 不等,具体取决于数组的大小。请注意,子数组的大小尽量是 2 的幂,这样 merge 函数性能表现会更好。

以下是对 TimSort 算法的逐步解释:

  • 使用插入排序将输入数组分成小的 run块。每个 run 块都为递增顺序。
  • 然后使用改进的归并排序算法合并 run 块。合并步骤的工作原理是比较 每个run 块的第一个元素,并将最小的元素添加到输出数组。该过程一直持续到所有元素都添加到输出数组。
  • 如果 run 块不是良构的,即有些不是按升序排列的,那么它们将合并在一起直到它们为良构的。
  • run 块的大小在每次迭代中增加两倍,直到整个数组排序完成。

TimSort 的想法是基于插入排序对小数组表现良好的事实,因此在最好情况下可以获得插入排序 O ( n ) O(n) O(n) 的最好性能。同时又能获得归并排序最差 O ( n log ⁡ n ) O(n\log n) O(nlogn) 的性能表现。

TimSort 详解

小数组用插入排序

正如前面 TimSort 算法原理讲到的,如果数组比较小(通常是小于 2 6 = 64 2^6=64 26=64),那么 TimSort 会直接采用插入排序对数组进行排序。

这是因为插入排序作为一种简单的排序算法,对小列表最有效。它在较大的列表中非常慢,但在小列表中非常快。 插入排序的思想如下:

  • 逐个扫一遍数组元素
  • 通过在正确位置插入元素来构建排序数组

插入排序相信大家都学过,原理也比较简单,这里不做过多赘述。下面这一张动图很好的演示了插入排序的过程。

img

图2. 插入排序过程演示

Run 块

如果列表比较大,则算法会先遍历列表,查找严格递增或递减的部分。如果该部分是递减的,则将其反转成递增的。

举个例子,假如数组元素是 [ 3 , 2 , 1 , 9 , 17 , 34 ] [3, 2, 1, 9, 17, 34] [3,2,1,9,17,34],遍历发现前3个元素是递减的,则 run 块会将其变为递增的,即 [ 1 , 2 , 3 , 9 , 17 , 34 ] [\bold{1,2,3},9,17,34] [1,2,3,9,17,34]

当 run 块的数量等于或略小于 2 的幂时,合并 2 个数组的效率会更高。Timsort 通过确保 minrun 等于或小于 2 的幂来保证合并的效率。 minrun 的取值范围一般在 32 到 64 之间(含)。选定的 minrun 值要确保原始数组的长度除以 minrun 后等于或略小于 2 的幂。

如果 run 块的长度小于 minrun,则计算该 run 块长度与 minrun 的偏离,看看 run 块还差多少元素并执行插入排序以创建新 run 块。

这部分完成后,我们得到一堆排序好的 run 块。

归并

这一步,Timsort 执行归并排序将 run 块合并在一起。这里,Timsort 需要确保在归并排序时保持稳定性和合并平衡。

为了保持稳定性,算法就不应该交换 2 个等值的数。这不仅保留了它们在列表中的原始位置,而且使算法更快。

当 Timsort 发现 run 块时,会将它们添加到栈中。栈是先进后出的。

Timsort 试图在归并排序 run 块时平衡两种相互竞争的需求。一方面,我们希望尽可能地延迟合并,以便利用稍后可能出现的模式。但我们更希望尽快进行合并,以利用刚刚发现的处于栈顶的 run 块,因此我们也不能将合并延迟“太久”,因为它会消耗更多内存来记住仍未合并的 run 块,并且栈的大小是有限的。

为了找到最优折中方案,Timsort 会跟踪栈中最近的三个项并规定如下 2 个法则:

  1. A > B + C A \gt B+C A>B+C
  2. B > C B \gt C B>C

其中 A , B , C A,B,C A,B,C 是栈中最近的三个项。用 Tim Peters 的原话说:

结果证明这是一个很好的折衷方案,在栈顶维护两个不变量,其中 A、B 和 C 是三个最右边尚未合并的切片的长度。

通常,将不同长度的相邻 run 块合并到位是很困难的。更难的是我们必须保持稳定。为了解决这个问题,Timsort 预留了临时内存。它将两个 run 块中较小的(同时调用 run A 和 run B)放入该临时内存中。

算法实现

下面给出 TimSort 的 Python 实现。

TimSort 依赖于插入排序和归并排序,我们首先实现这 2 种排序。

# insertionSort函数用插入排序从left到right排序数组arr
def insertionSort(arr, left, right):
    for i in range(left + 1, right + 1):
        j = i
        while j > left and arr[j] < arr[j - 1]:
            arr[j], arr[j - 1] = arr[j - 1], arr[j]
            j -= 1
# merge函数合并排序好的run块
def merge(arr, l, m, r):
 
    # 原数组一分为二:左数组和右数组
    len1, len2 = m - l + 1, r - m
    left, right = [], []
    for i in range(0, len1):
        left.append(arr[l + i])
    for i in range(0, len2):
        right.append(arr[m + 1 + i])
 
    i, j, k = 0, 0, l
 
    # 比较后将两个数组合并成一个更大的数组
    while i < len1 and j < len2:
        if left[i] <= right[j]:
            arr[k] = left[i]
            i += 1
 
        else:
            arr[k] = right[j]
            j += 1
 
        k += 1
 
    # 复制左数组遗留元素
    while i < len1:
        arr[k] = left[i]
        k += 1
        i += 1
 
    # 复制右数组遗留元素
    while j < len2:
        arr[k] = right[j]
        k += 1
        j += 1

计算 run 块的最小值,确保归并可以高效运行

MIN_MERGE = 32
 
# 计算run块的最小长度 
def calcMinRun(n):
    r = 0
    while n >= MIN_MERGE:
        r |= n & 1
        n >>= 1
    return n + r

TimSort过程

# TimSort排序
def timSort(arr):
    n = len(arr)
    minRun = calcMinRun(n)
 
    # 对大小为 RUN 的单个子数组进行排序
    for start in range(0, n, minRun):
        end = min(start + minRun - 1, n - 1)
        insertionSort(arr, start, end)
 
    # 从大小 RUN(或 32)开始合并。最终合并形成大小为2^n
    size = minRun
    while size < n:
        # 选择左子数组的起点。 
        # 合并 arr[left..left+size-1] 和 arr[left+size, left+2*size-1] 
        # 每次合并后,left 增加 2*size
        for left in range(0, n, 2 * size):
            # 查找左子数组的终点 
            # mid+1 为右子数组的起点
            mid = min(n - 1, left + size - 1)
            right = min((left + 2 * size - 1), (n - 1))
 
            # 合并子数组 arr[left.....mid] & arr[mid+1....right]
            if mid < right:
                merge(arr, left, mid, right)
 
        size = 2 * size    
if __name__ == "__main__":
    arr = [-2, 7, 15, -14, 0, 15, 0,
           7, -7, -4, -13, 5, 8, -14, 12]
 
    print("排序前")
    print(arr)

    timSort(arr)
 
    print("排序后")
    print(arr)

输出:

排序前
-2, 7, 15, -14, 0, 15, 0, 7, -7, -4, -13, 5, 8, -14, 12
排序后
-14  -14  -13  -7  -4  -2  0  0  5  7  7  8  12  15  15

总结

Timsort 实际上已经内置于 Python 中,上面给出的代码实现仅作为演示用。

在 Python 要使用 Timsort,只需 list.sort()sorted(list) 即可。

如果你想掌握 Timsort 的工作原理,我强烈建议你尝试自己实现一遍!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/24637.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【源码解析】EasyExcel导入导出源码解析

EasyExcel介绍 Java解析、生成Excel比较有名的框架有Apache poi、jxl。但他们都存在一个严重的问题就是非常的耗内存&#xff0c;poi有一套SAX模式的API可以一定程度的解决一些内存溢出的问题&#xff0c;但POI还是有一些缺陷&#xff0c;比如07版Excel解压缩以及解压后存储都…

动态规划-分割回文串 II

动态规划-分割回文串 II 1 题目描述2 示例2.1 示例 1&#xff1a;2.2 示例 2&#xff1a;2.3 示例 3&#xff1a;2.4 提示&#xff1a; 3 解题思路和方法3.1 解题思路3.1.1 确定状态3.1.2 转移方程3.1.3 初始条件和边界情况3.1.4 计算顺序3.1.5 回文串的判断方法 3.2 算法代码实…

华为OD机试真题B卷 Java 实现【最长子字符串的长度】

一、题目描述 给你一个字符串s,字符串s首尾相连组成一个环形,请你在环形中找出‘o’字符出现了偶数次最长子字符串的长度。 二、输入描述 输入一串小写字母组成的字符串。 三、输出描述 输出一个整数。 四、解题思路 题目要求在给定的环形字符串中找出字符’o’出现了…

软件测试之-测试用例写作规范

软件测试用例得出软件测试用例的内容&#xff0c;其次&#xff0c;按照软件测试写作方法&#xff0c;落实到文档中&#xff0c;两者是形式和内容的关系&#xff0c;好的测试用例不仅方便自己和别人查看&#xff0c;而且能帮助设计的时候考虑的更周。 一个好的测试用例必须包含…

STL-queue和priority_queue的模拟实现

回顾 对于STL&#xff0c;我们已经知道了vector和list&#xff0c;而它们是STL中被称为六大组件之一的容器&#xff0c;我们还学习了模拟实现stack&#xff0c;而stack在STL中被称为六大组件之一的适配器&#xff0c;今天&#xff0c;我们来学习queue的模拟实现和priority_que…

java 课程信息管理系统Myeclipse开发mysql数据库struts2结构java编程计算机网页项目

一、源码特点 java 课程信息管理系统 是一套完善的web设计系统&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为 TOMCAT7.0,Myeclipse8.5开发&#xff0c;数据库为Mysql&#xff0c;使…

javascript基础五:深拷贝浅拷贝的区别?如何实现一个深拷贝?

一、数据类型存储 JavaScript中存在两大数据类型&#xff1a; 基本类型引用类型 基本类型数据保存在在栈内存中 引用类型数据保存在堆内存中&#xff0c;引用数据类型的变量是一个指向堆内存中实际对象的引用&#xff0c;存在栈中 二、浅拷贝 浅拷贝&#xff0c;指的是创建新…

( 数组) 209. 长度最小的子数组——【Leetcode每日一题】

❓209. 长度最小的子数组 难度&#xff1a;中等 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] &#xff0c;并返回其长度。如果不存在符合条件的子数组&#xff0c;…

在线Excel绝配:SpreadJS 16.1.1+GcExcel 6.1.1 Crack

前端&#xff1a;SpreadJS 16.1.1 后端&#xff1a; GcExcel 6.1.1 全能 SpreadJS 16.1.1此版本的产品中包含以下功能和增强功能。 添加了各种输入掩码样式选项。 添加了在保护工作表时设置密码以及在取消保护时验证密码的支持。 增强了组合图以将其显示为仪表图。 添加了…

Tugraph的设计和源码初步解析

1. Tugraph Tugraph是一款开源的性能优秀的图数据库&#xff0c;该图数据库使用多版本的BTree作为数据的存储引擎&#xff0c;同时设置了点边数据在这个存储引擎上的布局&#xff08;主要考虑数据的局部性&#xff09;&#xff0c;从而达到高性能查询的目的。本文主要从Tugrap…

研发工程师玩转Kubernetes——自动扩缩容

在《研发工程师玩转Kubernetes——使用Deployment进行多副本维护》一文中&#xff0c;我们通过Deployment实现了多副本维护——即维持在一个确定数量的副本个数。而在现实场景中&#xff0c;我们往往需要根据服务的压力&#xff0c;采用水平&#xff08;横向&#xff09;扩容的…

Springboot +spring security,前后端分离时的security处理方案(二)

一.简介 在前后端分离这样的开发模式下&#xff0c;前后端的交互都是通过 JSON 来进行数据传递的&#xff0c;无论登录成功还是失败&#xff0c;都不会有服务端跳转或者客户端跳转之类的操作。 也就是说无论登录成功还是失败&#xff0c;服务端都会返回一段登录成功或失败的 …

使用【Python+Appium】实现自动化测试

一、环境准备 1.脚本语言&#xff1a;Python3.x IDE&#xff1a;安装Pycharm 2.安装Java JDK 、Android SDK 3.adb环境&#xff0c;path添加E:\Software\Android_SDK\platform-tools 4.安装Appium for windows&#xff0c;官网地址 Redirecting 点击下载按钮会到GitHub的…

解决dpdk reserve的内存返回的虚拟地址和iova地址一样的问题

1. 背景: 在ubuntu20.04上用dpdk API: rte_memzone_reserve_aligned("L1L2_PCIE_MEMORY", 1.5*1024*1024*1024, rte_socket_id(), RTE_MEMZONE_1GB|RTE_MEMZONE_IOVA_CONTIG, RTE_CACHE_LINE_SIZE); 分配1.5…

如何在 GNU Linux 上通过 Nvm 安装 Node 和 Npm?

Node.js 是一个流行的 JavaScript 运行时环境&#xff0c;用于开发服务器端和网络应用程序。它带有一个强大的软件包管理器 npm&#xff0c;可以方便地安装和管理 JavaScript 包和依赖项。在 GNU/Linux 系统上&#xff0c;使用 Nvm&#xff08;Node Version Manager&#xff09…

Framework开发环境搭建

Framework开发环境搭建 开启Android Framework之旅&#xff0c;一步步记录自己学习过程。 硬件配置 RAM&#xff1a;最低16GB&#xff0c;建议32GB&#xff0c;有条件64GB&#xff0c;内存越高&#xff0c;编译时间越短ROM&#xff1a;最低400GB&#xff0c;代码250GB构建15…

Svn安装

目录 一. 软件环境 二. SVN服务端 1. yum安装svn 2. 查看安装的文件列表 3. 建立版本库 3.1 修改数据存储默认位置 3.2 使用svnadmin建立版本库 4. 配制 4.1 添加用户 4.2 配制读写权限 4.3 配制服务 5. 启动服务 5.1 停止服务 5.2 启动服务 5.3 拉取项目 三.…

Zookeeper集群 + Kafka集群

Zookeeper 概述 Zookeeper 定义 Zookeeper是一个开源的分布式的&#xff0c;为分布式框架提供协调服务的Apache项目。 Zookeeper 工作机制 Zookeeper从设计模式角度来理解&#xff1a;是一个基于观察者模式设计的分布式服务管理框架&#xff0c;它负责存储和管理大家都关心的…

CodeForces.1786A2.发牌.[中等][flg标识][数学规律][双色牌]

题目描述&#xff1a; 题目解读&#xff1a; 发牌问题&#xff0c;给两人发双色牌&#xff0c;同样还是 给a发1张&#xff0c;然后给b发2&#xff0c;3张&#xff1b; 给a发4&#xff0c;5张&#xff0c;给b发6&#xff0c;7张&#xff1b; 给a发8&#xff0c;9张&#xff…

《最新出炉》Python+Playwright自动化测试-2-playwright的API及其他知识

一.简介 上一篇我已经将PythonPlaywright的环境搭建好了&#xff0c;而且也简单的演示了一下三款浏览器的启动和关闭&#xff0c;是不是很简单啊。今天主要是把一篇的中的代码进行一次详细的注释&#xff0c;然后说一下playwright的API和其他相关知识点。那么首先将上一篇中的…
最新文章