简易版的TimSort排序算法

轻伟小哥_4985

轻伟小哥_4985

2016-10-31

2333人浏览

原创

1. 简易版本TimSort排序算法原理与实现

timsort排序算法是python和java针对对象数组的默认排序算法。timsort排序算法的本质是归并排序算法,只是在归并排序算法上进行了大量的优化。对于日常生活中我们需要排序的数据通常不是完全随机的,而是部分有序的,或者部分逆序的,所以timsort充分利用已有序的部分进行归并排序。现在我们提供一个简易版本timsort排序算法,它主要做了以下优化:

1.1利用原本已有序的片段

首先规定一个最小归并长度。检查数组中原本有序的片段,如果已有序的长度小于规定的最小归并长度,则通过插入排序对已有序的片段进行进行扩充(这样做的原因避免归并长度较小的片段,因为这样的效率比较低)。将有序片段的起始索引位置和已有序的长度入栈。

1.2避免一个较长的有序片段和一个较小的有序片段进行归并,因为这样的效率比较低:

(1)如果栈中存在已有序的至少三个序列,我们用X,Y,Z依次表示从栈顶向下的三个已有序列片段,当三者的长度满足X+Y>=Z时进行归并。

   (1.1)如果X是三者中长度最大的,先将X,Y,Z出栈,应该先归并Y和Z,然后将Y和Z归并的结果入栈,最后X入栈

   (1.2)否则将X和Y出栈,归并后结果入栈。注意,实际上我们不会真正的出栈,写代码中有一些技巧可以达到相同的效果,而且效率更高。

(2)如果不满足X+Y>=Z的条件或者栈中仅存在两个序列,我们用X,Y依次表示从栈顶向下的两个已有序列的长度,如果X>=Y则进行归并,然后将归并后的有序片段结果入栈。

1.3在归并两个已有序的片段时,采用了所谓的飞奔(gallop)模式,这样可以减少参与归并的数据长度

假设需要归并的两个已有序片段分别为X和Y,如果X片段的前m个元素都比Y片段的首元素小,那么这m个元素实际上是不需要参与归并的,因为归并后这m个元素仍然位于原来的位置。同理如果Y片段的最后n个元素都比X的最后一个元素大,那么Y的最后n个元素也不必参与归并。这样就减少了归并数组的长度(简易版没有这么做),也较少了待排序数组与辅助数组之间数据来回复制的长度,进而提高了归并的效率。

FilePond 灵活的 JavaScript 文件上传库
FilePond 灵活的 JavaScript 文件上传库

FilePond 是一个 JavaScript 文件上传库,支持通过拖拽、粘贴和 API 方式处理文件、目录、URL 和 Data URI。它包含内置的图像优化功能、异步分块上传功能,并提供了适用于 React、Vue、Angular 和 Svelte 的适配器。

下载

2. Java源代码

package datastruct;
 
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
 
public class SimpleTimSort<t>>{
    //最小归并长度
    private static final int MIN_MERGE = 16;
    //待排序数组
    private final T[] a;
    //辅助数组
    private T[] aux;
    //用两个数组表示栈
    private int[] runsBase = new int[40];
    private int[] runsLen = new int[40];
    //表示栈顶指针
    private int stackTop = 0;
     
    @SuppressWarnings("unchecked")
    public SimpleTimSort(T[] a){
        this.a = a;
        aux = (T[]) Array.newInstance(a[0].getClass(), a.length);
    }
     
    //T[from, to]已有序,T[to]以后的n元素插入到有序的序列中
    private void insertSort(T[] a, int from, int to, int n){
        int i = to + 1;
        while(n > 0){
            T tmp = a[i];
            int j;
            for(j = i-1; j >= from && tmp.compareTo(a[j]) = a.length){//超出范围
            return 0;
        }
         
        if(i == a.length-1){//只有一个元素
            return 1;
        }
         
        //至少两个元素
        if(a[i].compareTo(a[i+1]) =的情况,否则不能保证稳定性
            while(i+1  0){
                i++;
                n++;
            }
            //对降序片段逆序
            int j = from;
            while(j  1){//至少两个run序列
            int x = stackTop - 2;
            //x > 0 表示至少三个run序列
            if(x > 0 && runsLen[x-1] = 0){
                i++;
            }else{
                break;
            }
        }
        return i;
    }
     
    //返回前一个片段的末元素在后一个片段应该位于的位置
    private int gallopRight(T[] a, int base, int len, T key){
        int i = base + len -1;
        while(i >= base){
            if(key.compareTo(a[i])  iend){
                a[k] = aux[j++];
            }else
            if(j > jend){
                a[k] = aux[i++];
            }else
            if(aux[i].compareTo(aux[j])  1){
            mergeAt(stackTop-2);
        }
    }
     
    //timSort的主方法
    public void timSort(){
        //n表示剩余长度
        int n = a.length; 
         
        if(n  0){
            int len = maxAscendingLen(a, base);
            if(len  MIN_MERGE ?  MIN_MERGE - len : n - len;
                insertSort(a, base, base + len-1, abscent);
                len = len + abscent;
            }
            pushRun(base, len);
            n = n - len;
            base = base + len;
             
            int x;
            while((x  = needMerge()) >= 0 ){
                mergeAt(x);
            }
        }
        forceMerge();
    }
     
    public static void main(String[] args){
         
        //随机产生测试用例
        Random rnd = new Random(System.currentTimeMillis());
        boolean flag = true;
        while(flag){
             
            //首先产生一个全部有序的数组
            Integer[] arr1 = new Integer[1000];
            for(int i = 0; i = arr1.length){
                    continue;
                }
                while(x  sts = new SimpleTimSort<integer>(arr1);
            sts.timSort();
             
            //比较SimpleTimSort排序和库函数提供的排序结果比较是否一致
            //如果没有打印任何结果,说明排序结果正确
            if(!Arrays.deepEquals(arr1, arr2)){
                for(int i = 0; i <p style="margin: 20px 0px; padding: 0px; font-size: 21px; line-height: 1.5; color: rgb(51, 51, 51); font-family: Verdana, Arial, Helvetica, sans-serif; white-space: normal; background-color: rgb(255, 255, 255);">3.TimSort算法应当注意的问题</p>
<p>TimSort算法只会对连续的两个片段进行归并,这样才能保证算法的稳定性。</p>
<p>最小归并长度和栈的长度存在一定的关系,如果增大最小归并长度,则栈的长度也应该增大,否则可能引起栈越界的风险(代码中栈是通过长度为40的数组来实现的)。</p>
<p style="margin: 20px 0px; padding: 0px; font-size: 21px; line-height: 1.5; color: rgb(51, 51, 51); font-family: Verdana, Arial, Helvetica, sans-serif; white-space: normal; background-color: rgb(255, 255, 255);">4.完整版的TimSort算法</p>
<p>实际上,完整版的TimSort算法会在上述简易TimSort算法上还有大量的优化。比如有序序列小于最小归并长度时,我们可以利用类似二分查找的方式来找到应该插入的位置来对数组进行长度扩充。再比如飞奔模式中采用二分查找的方式查找第二个序列的首元素在第一个序列的位置,同时还可以使用较小的辅助空间完成归并,有兴趣的同学可以查看Java中的源代码来学习。</p>
<p><br></p></integer></t>

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

java

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

2026.11.17

20

15

GoFrame框架安装与gf命令行工具
GoFrame框架安装与gf命令行工具

本专题围绕GoFrame框架的安装与工具链配置展开,讲清Go版本要求、gf命令行的安装方式、代理镜像与依赖准备,说明项目初始化、热编译、交叉编译打包的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.17

60

15

GoFrame框架零基础入门
GoFrame框架零基础入门

本专题整理GoFrame框架的入门知识,从模块化设计理念、环境准备到跑通第一个Web服务,讲清目录分层、配置加载、日志与中间件的用法,并对比Gin、Go-Zero的差异,帮助Go开发者建立整体认知。

2026.11.17

60

15

SQLAlchemy 一对多关系怎么建立
SQLAlchemy 一对多关系怎么建立

SQLAlchemy 一对多关系怎么建立?本专题整理父子表外键、relationship 双向映射、关联查询、级联删除和加载优化等相关文章,帮助你理解并实现常见的 ORM 关系建模。

2026.11.17

20

10

SQLAlchemy 如何增删改查
SQLAlchemy 如何增删改查

SQLAlchemy 如何增删改查?本专题整理 ORM 新增记录、条件查询、更新和删除、Session 事务提交与批量处理等实用文章,帮助你掌握 Python 数据库操作流程。

2026.11.17

60

11

SQLAlchemy ORM 模型怎么写
SQLAlchemy ORM 模型怎么写

SQLAlchemy ORM 模型怎么写?本专题整理模型类定义、Mapped 字段映射、主键与约束、表结构创建和常见报错的相关文章,帮助你从基础配置到实际建模逐步掌握 SQLAlchemy。

2026.11.17

40

16

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

180

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

140

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

160

15

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
dev.java 官方:Learn Java
dev.java 官方:Learn Java

共0课时 | 0人学习

Java JDBC数据库连接官方教程
Java JDBC数据库连接官方教程

共0课时 | 0人学习