和龙虾写的排序 Tim 排序

APPLEUFO

http://oi-wiki.com/basic/tim-sort/
Tim 排序

[color=rgba(0, 0, 0, 0.87)]本页面将介绍 Tim 排序（Timsort），一种混合的、稳定的排序算法．

引入

[color=rgba(0, 0, 0, 0.87)]Timsort 由 Python 核心开发者 Tim Peters 于 2002 年设计，并应用于 Python 语言，其巧妙结合了插入排序和归并排序的优点，针对数据集中的有序性进行了精确的优化，尤其适合处理包含大量部分有序子序列的数据集．自 Python 2.3 版本以来，Timsort 被选为 Python 标准库的默认排序算法，并被广泛应用于其他编程环境，例如在 Java SE 7 中被用于对非原始对象数组进行排序．

[color=rgba(0, 0, 0, 0.87)]和龙虾调试半天弄出来 经过测试  

[color=rgba(0, 0, 0, 0.87)]在 易语言里面  倒是对比普通 的   递归归并，迭代归并排序没啥优势    而且代码太复杂

[color=rgba(0, 0, 0, 0.87)]压缩包里带了龙虾写的快排的递归版，和迭代版

WorkBuddy

太好了！Tim Sort 终于跑通了！

这个可靠版的核心结构很清晰：

计算最小Run - 用位运算找到合适的Run大小（32-64之间）

构建Runs - 识别自然有序序列，不足的用插入排序扩展

自底向上归并 - 按宽度倍增的方式逐层归并

你现在的代码已经完整实现了标准Tim Sort的三阶段流程：

自然Run识别（还能检测降序并反转）

插入排序扩展短Run

标准归并

  

窗口程序集名	保 留	保 留	备 注
程序集3

子程序名	返回值类型	公开	备 注
排序_Tim排序_可靠版			从小到大
参数名	类 型	参考	可空	数组	备 注
参数_数组	整数型

变量名	类 型	静态	数组	备 注
局变_数组长度	整数型
局变_最小Run	整数型
局变_临时数组	整数型		0

局变_数组长度 ＝ 取数组成员数 (参数_数组)
如果 (局变_数组长度 ＜ 2)
返回 ()



' 分配临时数组用于归并
重定义数组 (局变_临时数组, 假, 局变_数组长度)
局变_最小Run ＝ 计算最小Run (局变_数组长度)
' 第一阶段：构建有序Run（自然Run识别 + 插入排序扩展）
Tim排序_构建Runs (参数_数组, 局变_数组长度, 局变_最小Run)
' 第二阶段：标准自底向上归并
Tim排序_自底向上归并 (参数_数组, 局变_临时数组, 局变_数组长度, 局变_最小Run)

子程序名	返回值类型	公开	备 注
计算最小Run	整数型
参数名	类 型	参考	可空	数组	备 注
参数_数组长度	整数型

变量名	类 型	静态	数组	备 注
局变_R	整数型

局变_R ＝ 0
判断循环首 (参数_数组长度 ≥ 64)
局变_R ＝ 位或 (局变_R, 位与 (参数_数组长度, 1))
参数_数组长度 ＝ 右移 (参数_数组长度, 1)
判断循环尾 ()
返回 (参数_数组长度 ＋ 局变_R)

子程序名	返回值类型	公开	备 注
识别自然Run	整数型
参数名	类 型	参考	可空	数组	备 注
参数_数组	整数型
参数_起始位置	整数型
参数_剩余长度	整数型

变量名	类 型	静态	数组	备 注
局变_当前位置	整数型
局变_是升序	逻辑型

如果 (参数_剩余长度 ＝ 1)
返回 (1)



局变_当前位置 ＝ 参数_起始位置 ＋ 1
' 判断升序还是降序
如果 (参数_数组 [局变_当前位置] ≥ 参数_数组 [局变_当前位置 － 1])
局变_是升序 ＝ 真
' 升序扩展
判断循环首 (局变_当前位置 ＜ 参数_起始位置 ＋ 参数_剩余长度)
如果 (参数_数组 [局变_当前位置] ＜ 参数_数组 [局变_当前位置 － 1])
跳出循环 ()


局变_当前位置 ＝ 局变_当前位置 ＋ 1
判断循环尾 ()
局变_是升序 ＝ 假
' 降序扩展
判断循环首 (局变_当前位置 ＜ 参数_起始位置 ＋ 参数_剩余长度)
如果 (参数_数组 [局变_当前位置] ＞ 参数_数组 [局变_当前位置 － 1])
跳出循环 ()


局变_当前位置 ＝ 局变_当前位置 ＋ 1
判断循环尾 ()
' 反转降序Run
Tim排序_反转 (参数_数组, 参数_起始位置, 局变_当前位置 － 1)

返回 (局变_当前位置 － 参数_起始位置)

子程序名	返回值类型	公开	备 注
Tim排序_反转
参数名	类 型	参考	可空	数组	备 注
参数_数组	整数型
参数_左边界	整数型
参数_右边界	整数型

判断循环首 (参数_左边界 ＜ 参数_右边界)
交换变量 (参数_数组 [参数_左边界], 参数_数组 [参数_右边界])
参数_左边界 ＝ 参数_左边界 ＋ 1
参数_右边界 ＝ 参数_右边界 － 1
判断循环尾 ()

子程序名	返回值类型	公开	备 注
Tim排序_构建Runs
参数名	类 型	参考	可空	数组	备 注
参数_数组	整数型
参数_数组长度	整数型
参数_最小Run	整数型

变量名	类 型	静态	数组	备 注
局变_起始位置	整数型
局变_剩余长度	整数型
局变_Run长度	整数型
局变_扩展长度	整数型

局变_起始位置 ＝ 1
局变_剩余长度 ＝ 参数_数组长度
判断循环首 (局变_剩余长度 ＞ 0)
局变_Run长度 ＝ 识别自然Run (参数_数组, 局变_起始位置, 局变_剩余长度)
' 扩展Run
如果 (局变_Run长度 ＜ 参数_最小Run)
局变_扩展长度 ＝ 参数_最小Run
如果 (局变_扩展长度 ＞ 局变_剩余长度)
局变_扩展长度 ＝ 局变_剩余长度



' 用插入排序扩展 [起始位置+Run长度, 起始位置+扩展长度-1]
插入排序扩展 (参数_数组, 局变_起始位置, 局变_起始位置 ＋ 局变_Run长度 － 1, 局变_起始位置 ＋ 局变_扩展长度 － 1)
局变_Run长度 ＝ 局变_扩展长度



局变_起始位置 ＝ 局变_起始位置 ＋ 局变_Run长度
局变_剩余长度 ＝ 局变_剩余长度 － 局变_Run长度
判断循环尾 ()

子程序名	返回值类型	公开	备 注
插入排序扩展
参数名	类 型	参考	可空	数组	备 注
参数_数组	整数型
参数_Run起始	整数型
参数_Run结束	整数型
参数_扩展结束	整数型

变量名	类 型	静态	数组	备 注
局变_i	整数型
局变_j	整数型
局变_当前值	整数型

' 将 [Run结束+1, 扩展结束] 的元素插入到 [Run起始, Run结束] 中
计次循环首 (参数_扩展结束 － 参数_Run结束, 局变_i)
局变_当前值 ＝ 参数_数组 [参数_Run结束 ＋ 局变_i]
局变_j ＝ 参数_Run结束 ＋ 局变_i － 1
' 在已排序部分找插入位置
判断循环首 (局变_j ≥ 参数_Run起始 且 参数_数组 [局变_j] ＞ 局变_当前值)
参数_数组 [局变_j ＋ 1] ＝ 参数_数组 [局变_j]
局变_j ＝ 局变_j － 1
判断循环尾 ()
参数_数组 [局变_j ＋ 1] ＝ 局变_当前值
计次循环尾 ()

子程序名	返回值类型	公开	备 注
Tim排序_自底向上归并
参数名	类 型	参考	可空	数组	备 注
参数_数组	整数型
参数_临时数组	整数型
参数_数组长度	整数型
参数_最小Run	整数型

变量名	类 型	静态	数组	备 注
局变_宽度	整数型
局变_i	整数型
局变_左起始	整数型
局变_中间位置	整数型
局变_右结束	整数型

局变_宽度 ＝ 参数_最小Run
判断循环首 (局变_宽度 ＜ 参数_数组长度)
局变_i ＝ 1
判断循环首 (局变_i ≤ 参数_数组长度)
局变_左起始 ＝ 局变_i
局变_中间位置 ＝ 局变_i ＋ 局变_宽度 － 1
如果 (局变_中间位置 ≥ 参数_数组长度)
跳出循环 ()



局变_右结束 ＝ 局变_i ＋ 局变_宽度 × 2 － 1
如果 (局变_右结束 ＞ 参数_数组长度)
局变_右结束 ＝ 参数_数组长度



' 归并 [左起始, 中间位置] 和 [中间位置+1, 右结束]
标准归并 (参数_数组, 参数_临时数组, 局变_左起始, 局变_中间位置, 局变_右结束)
局变_i ＝ 局变_i ＋ 局变_宽度 × 2
判断循环尾 ()
局变_宽度 ＝ 局变_宽度 × 2
判断循环尾 ()

子程序名	返回值类型	公开	备 注
标准归并
参数名	类 型	参考	可空	数组	备 注
参数_数组	整数型
参数_临时数组	整数型
参数_左边界	整数型
参数_中间位置	整数型
参数_右边界	整数型

变量名	类 型	静态	数组	备 注
局变_i	整数型
局变_j	整数型
局变_k	整数型

' 复制到临时数组
计次循环首 (参数_中间位置 － 参数_左边界 ＋ 1, 局变_i)
参数_临时数组 [参数_左边界 ＋ 局变_i － 1] ＝ 参数_数组 [参数_左边界 ＋ 局变_i － 1]
计次循环尾 ()
计次循环首 (参数_右边界 － 参数_中间位置, 局变_i)
参数_临时数组 [参数_中间位置 ＋ 局变_i] ＝ 参数_数组 [参数_中间位置 ＋ 局变_i]
计次循环尾 ()
' 归并
局变_i ＝ 参数_左边界
局变_j ＝ 参数_中间位置 ＋ 1
局变_k ＝ 参数_左边界
判断循环首 (局变_i ≤ 参数_中间位置 且 局变_j ≤ 参数_右边界)
如果 (参数_临时数组 [局变_i] ≤ 参数_临时数组 [局变_j])
参数_数组 [局变_k] ＝ 参数_临时数组 [局变_i]
局变_i ＝ 局变_i ＋ 1
参数_数组 [局变_k] ＝ 参数_临时数组 [局变_j]
局变_j ＝ 局变_j ＋ 1
局变_k ＝ 局变_k ＋ 1
判断循环尾 ()
' 复制剩余
计次循环首 (参数_中间位置 － 局变_i ＋ 1, )
参数_数组 [局变_k] ＝ 参数_临时数组 [局变_i]
局变_i ＝ 局变_i ＋ 1
局变_k ＝ 局变_k ＋ 1
计次循环尾 ()
计次循环首 (参数_右边界 － 局变_j ＋ 1, )
参数_数组 [局变_k] ＝ 参数_临时数组 [局变_j]
局变_j ＝ 局变_j ＋ 1
局变_k ＝ 局变_k ＋ 1
计次循环尾 ()

.版本 2<br /> <br /> .程序集 程序集3<br /> <br /> .子程序 排序_Tim排序_可靠版, , 公开, 从小到大<br /> .参数 参数_数组, 整数型, 数组<br /> .局部变量 局变_数组长度, 整数型<br /> .局部变量 局变_最小Run, 整数型<br /> .局部变量 局变_临时数组, 整数型, , "0"<br /> <br /> 局变_数组长度 ＝ 取数组成员数 (参数_数组)<br /> .如果 (局变_数组长度 ＜ 2)<br />     返回 ()<br /> .否则<br /> <br /> .如果结束<br /> <br /> ' 分配临时数组用于归并<br /> 重定义数组 (局变_临时数组, 假, 局变_数组长度)<br /> <br /> 局变_最小Run ＝ 计算最小Run (局变_数组长度)<br /> <br /> ' 第一阶段：构建有序Run（自然Run识别 + 插入排序扩展）<br /> Tim排序_构建Runs (参数_数组, 局变_数组长度, 局变_最小Run)<br /> <br /> ' 第二阶段：标准自底向上归并<br /> Tim排序_自底向上归并 (参数_数组, 局变_临时数组, 局变_数组长度, 局变_最小Run)<br /> <br /> .子程序 计算最小Run, 整数型<br /> .参数 参数_数组长度, 整数型<br /> .局部变量 局变_R, 整数型<br /> <br /> 局变_R ＝ 0<br /> .判断循环首 (参数_数组长度 ≥ 64)<br />     局变_R ＝ 位或 (局变_R, 位与 (参数_数组长度, 1))<br />     参数_数组长度 ＝ 右移 (参数_数组长度, 1)<br /> .判断循环尾 ()<br /> <br /> 返回 (参数_数组长度 ＋ 局变_R)<br /> <br /> .子程序 识别自然Run, 整数型<br /> .参数 参数_数组, 整数型, 数组<br /> .参数 参数_起始位置, 整数型<br /> .参数 参数_剩余长度, 整数型<br /> .局部变量 局变_当前位置, 整数型<br /> .局部变量 局变_是升序, 逻辑型<br /> <br /> .如果 (参数_剩余长度 ＝ 1)<br />     返回 (1)<br /> .否则<br /> <br /> .如果结束<br /> <br /> 局变_当前位置 ＝ 参数_起始位置 ＋ 1<br /> <br /> ' 判断升序还是降序<br /> .如果 (参数_数组 [局变_当前位置] ≥ 参数_数组 [局变_当前位置 － 1])<br />     局变_是升序 ＝ 真<br />     ' 升序扩展<br />     .判断循环首 (局变_当前位置 ＜ 参数_起始位置 ＋ 参数_剩余长度)<br />         .如果 (参数_数组 [局变_当前位置] ＜ 参数_数组 [局变_当前位置 － 1])<br />             跳出循环 ()<br />         .否则<br /> <br />         .如果结束<br />         局变_当前位置 ＝ 局变_当前位置 ＋ 1<br />     .判断循环尾 ()<br /> .否则<br />     局变_是升序 ＝ 假<br />     ' 降序扩展<br />     .判断循环首 (局变_当前位置 ＜ 参数_起始位置 ＋ 参数_剩余长度)<br />         .如果 (参数_数组 [局变_当前位置] ＞ 参数_数组 [局变_当前位置 － 1])<br />             跳出循环 ()<br />         .否则<br /> <br />         .如果结束<br />         局变_当前位置 ＝ 局变_当前位置 ＋ 1<br />     .判断循环尾 ()<br /> <br />     ' 反转降序Run<br />     Tim排序_反转 (参数_数组, 参数_起始位置, 局变_当前位置 － 1)<br /> .如果结束<br /> <br /> 返回 (局变_当前位置 － 参数_起始位置)<br /> <br /> .子程序 Tim排序_反转<br /> .参数 参数_数组, 整数型, 数组<br /> .参数 参数_左边界, 整数型<br /> .参数 参数_右边界, 整数型<br /> <br /> .判断循环首 (参数_左边界 ＜ 参数_右边界)<br />     交换变量 (参数_数组 [参数_左边界], 参数_数组 [参数_右边界])<br />     参数_左边界 ＝ 参数_左边界 ＋ 1<br />     参数_右边界 ＝ 参数_右边界 － 1<br /> .判断循环尾 ()<br /> <br /> .子程序 Tim排序_构建Runs<br /> .参数 参数_数组, 整数型, 数组<br /> .参数 参数_数组长度, 整数型<br /> .参数 参数_最小Run, 整数型<br /> .局部变量 局变_起始位置, 整数型<br /> .局部变量 局变_剩余长度, 整数型<br /> .局部变量 局变_Run长度, 整数型<br /> .局部变量 局变_扩展长度, 整数型<br /> <br /> 局变_起始位置 ＝ 1<br /> 局变_剩余长度 ＝ 参数_数组长度<br /> <br /> .判断循环首 (局变_剩余长度 ＞ 0)<br />     局变_Run长度 ＝ 识别自然Run (参数_数组, 局变_起始位置, 局变_剩余长度)<br /> <br />     ' 扩展Run<br />     .如果 (局变_Run长度 ＜ 参数_最小Run)<br />         局变_扩展长度 ＝ 参数_最小Run<br />         .如果 (局变_扩展长度 ＞ 局变_剩余长度)<br />             局变_扩展长度 ＝ 局变_剩余长度<br />         .否则<br /> <br />         .如果结束<br /> <br />         ' 用插入排序扩展 [起始位置+Run长度, 起始位置+扩展长度-1]<br />         插入排序扩展 (参数_数组, 局变_起始位置, 局变_起始位置 ＋ 局变_Run长度 － 1, 局变_起始位置 ＋ 局变_扩展长度 － 1)<br />         局变_Run长度 ＝ 局变_扩展长度<br />     .否则<br /> <br />     .如果结束<br /> <br />     局变_起始位置 ＝ 局变_起始位置 ＋ 局变_Run长度<br />     局变_剩余长度 ＝ 局变_剩余长度 － 局变_Run长度<br /> .判断循环尾 ()<br /> <br /> .子程序 插入排序扩展<br /> .参数 参数_数组, 整数型, 数组<br /> .参数 参数_Run起始, 整数型<br /> .参数 参数_Run结束, 整数型<br /> .参数 参数_扩展结束, 整数型<br /> .局部变量 局变_i, 整数型<br /> .局部变量 局变_j, 整数型<br /> .局部变量 局变_当前值, 整数型<br /> <br /> ' 将 [Run结束+1, 扩展结束] 的元素插入到 [Run起始, Run结束] 中<br /> .计次循环首 (参数_扩展结束 － 参数_Run结束, 局变_i)<br />     局变_当前值 ＝ 参数_数组 [参数_Run结束 ＋ 局变_i]<br />     局变_j ＝ 参数_Run结束 ＋ 局变_i － 1<br /> <br />     ' 在已排序部分找插入位置<br />     .判断循环首 (局变_j ≥ 参数_Run起始 且 参数_数组 [局变_j] ＞ 局变_当前值)<br />         参数_数组 [局变_j ＋ 1] ＝ 参数_数组 [局变_j]<br />         局变_j ＝ 局变_j － 1<br />     .判断循环尾 ()<br /> <br />     参数_数组 [局变_j ＋ 1] ＝ 局变_当前值<br /> .计次循环尾 ()<br /> <br /> .子程序 Tim排序_自底向上归并<br /> .参数 参数_数组, 整数型, 数组<br /> .参数 参数_临时数组, 整数型, 数组<br /> .参数 参数_数组长度, 整数型<br /> .参数 参数_最小Run, 整数型<br /> .局部变量 局变_宽度, 整数型<br /> .局部变量 局变_i, 整数型<br /> .局部变量 局变_左起始, 整数型<br /> .局部变量 局变_中间位置, 整数型<br /> .局部变量 局变_右结束, 整数型<br /> <br /> 局变_宽度 ＝ 参数_最小Run<br /> <br /> .判断循环首 (局变_宽度 ＜ 参数_数组长度)<br />     局变_i ＝ 1<br />     .判断循环首 (局变_i ≤ 参数_数组长度)<br />         局变_左起始 ＝ 局变_i<br />         局变_中间位置 ＝ 局变_i ＋ 局变_宽度 － 1<br />         .如果 (局变_中间位置 ≥ 参数_数组长度)<br />             跳出循环 ()<br />         .否则<br /> <br />         .如果结束<br /> <br />         局变_右结束 ＝ 局变_i ＋ 局变_宽度 × 2 － 1<br />         .如果 (局变_右结束 ＞ 参数_数组长度)<br />             局变_右结束 ＝ 参数_数组长度<br />         .否则<br /> <br />         .如果结束<br /> <br />         ' 归并 [左起始, 中间位置] 和 [中间位置+1, 右结束]<br />         标准归并 (参数_数组, 参数_临时数组, 局变_左起始, 局变_中间位置, 局变_右结束)<br /> <br />         局变_i ＝ 局变_i ＋ 局变_宽度 × 2<br />     .判断循环尾 ()<br /> <br />     局变_宽度 ＝ 局变_宽度 × 2<br /> .判断循环尾 ()<br /> <br /> .子程序 标准归并<br /> .参数 参数_数组, 整数型, 数组<br /> .参数 参数_临时数组, 整数型, 数组<br /> .参数 参数_左边界, 整数型<br /> .参数 参数_中间位置, 整数型<br /> .参数 参数_右边界, 整数型<br /> .局部变量 局变_i, 整数型<br /> .局部变量 局变_j, 整数型<br /> .局部变量 局变_k, 整数型<br /> <br /> ' 复制到临时数组<br /> .计次循环首 (参数_中间位置 － 参数_左边界 ＋ 1, 局变_i)<br />     参数_临时数组 [参数_左边界 ＋ 局变_i － 1] ＝ 参数_数组 [参数_左边界 ＋ 局变_i － 1]<br /> .计次循环尾 ()<br /> <br /> .计次循环首 (参数_右边界 － 参数_中间位置, 局变_i)<br />     参数_临时数组 [参数_中间位置 ＋ 局变_i] ＝ 参数_数组 [参数_中间位置 ＋ 局变_i]<br /> .计次循环尾 ()<br /> <br /> ' 归并<br /> 局变_i ＝ 参数_左边界<br /> 局变_j ＝ 参数_中间位置 ＋ 1<br /> 局变_k ＝ 参数_左边界<br /> <br /> .判断循环首 (局变_i ≤ 参数_中间位置 且 局变_j ≤ 参数_右边界)<br />     .如果 (参数_临时数组 [局变_i] ≤ 参数_临时数组 [局变_j])<br />         参数_数组 [局变_k] ＝ 参数_临时数组 [局变_i]<br />         局变_i ＝ 局变_i ＋ 1<br />     .否则<br />         参数_数组 [局变_k] ＝ 参数_临时数组 [局变_j]<br />         局变_j ＝ 局变_j ＋ 1<br />     .如果结束<br />     局变_k ＝ 局变_k ＋ 1<br /> .判断循环尾 ()<br /> <br /> ' 复制剩余<br /> .计次循环首 (参数_中间位置 － 局变_i ＋ 1, )<br />     参数_数组 [局变_k] ＝ 参数_临时数组 [局变_i]<br />     局变_i ＝ 局变_i ＋ 1<br />     局变_k ＝ 局变_k ＋ 1<br /> .计次循环尾 ()<br /> <br /> .计次循环首 (参数_右边界 － 局变_j ＋ 1, )<br />     参数_数组 [局变_k] ＝ 参数_临时数组 [局变_j]<br />     局变_j ＝ 局变_j ＋ 1<br />     局变_k ＝ 局变_k ＋ 1<br /> .计次循环尾 ()

一指温柔

感谢分享

china5jin

看着好像很牛逼的样子,学习了

kyo9766

看看速度怎么样，感谢分享

year1970

感谢分享

lassgo

龙虾写的？这Tim排序怕不是海鲜味儿的吧，哈哈，链接先收藏了，回头细品！

刀子嘴豆腐心

搜索看看干嘛用的

qqmqqg

66666666666666666

胖子葛格

感谢大神分享~！

wgqxj

谢谢分享