混合归并排序 不固定步长 和龙虾写的

APPLEUFO

只能用于整数型，想用与 文本型  改改就是了  

原来的归并是固定步长   现在不固定     对完全方向相反，最差情况有奇效 ，可用直接反转数组完事

混合归并排序原理
一句话概括
首趟扫描找自然段边界，后续轮次复用边界做归并，不再重新扫描。

三个阶段
1. 扫描自然段（只做一次，O(n)）

从左到右扫一遍数组，遇到 a > a[i+1] 就是一个"降序断点"，说明前面的自然升序段结束了。把每个段的起始下标存到 游标首[]，结束下标存到 游标尾_[]。

比如 [3,7,12, 5,9, 2, 6,8,15, 1,4,10] 一趟扫完，分段计数 = 5，每个段的边界都记录好了。

2. 快速判断（O(1)）

扫描完看分段计数：

分段计数 = 1 → 整个数组已经升序，直接返回
分段计数 = 个数 → 每个元素自成一档，说明完全降序，反转即可
这两个极端场景不用归并，白捡 O(n) 甚至 O(1) 的性能。

3. 多轮归并（核心循环）

每轮做的事：

合并循环：步长为 2 遍历分段，相邻两段调 子程序_合并4 做两路归并。落单的段（奇数个分段时最后那个）传 右首=0, 右尾=0，子程序检测到直接 内存拷贝 复制过去不合并。
边界更新循环：同样步长为 2，游标首[m1] = 游标首[n1]（新段头 = 左段头），游标尾_[m1] = 游标尾_[n1+1]（新段尾 = 右段尾）。落单的段尾就是它自己的尾。
分段计数变成 (分段计数+1) \ 2（大概减半）
局变_源是临时 取反，切换源/目标数组
4. 双缓冲交替写入

关键优化：不每轮全数组拷贝。用 参数_数组 和 临时_归并 两个数组交替当源和目标：

第1轮：原数组 → 临时数组
第2轮：临时数组 → 原数组
第3轮：原数组 → 临时数组
...
最后如果数据落在临时数组里，用 参数_数组 = 局变_临时_归并 一次性拷回。

和其他归并排序的区别
普通归并        自然归并        混合归并
初始分段        固定步长1        扫描自然段        扫描自然段
后续轮次        步长翻倍        重新扫描        复用边界
完全升序        O(n log n)        O(n)        O(n)
完全随机        O(n log n)        O(n log n) + 扫描        O(n log n)
额外开销        无        每轮O(n)扫描        只1次扫描 + 边界数组
混合归并 = 自然归并的发现能力 + 普通归并的扫描效率。首趟扫描利用了数据的自然有序性（少段就少合并），后续轮次不再扫描又省掉了自然归并每轮 O(n) 的额外开销。

  

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

子程序名	返回值类型	公开	备 注
排序模块_混合归并排序4
参数名	类 型	参考	可空	数组	备 注
参数_数组	整数型
参数_升序	逻辑型

变量名	类 型	静态	数组	备 注
局变_个数	整数型
局变_分段计数	整数型
局变_游标首	整数型		0
局变_游标尾_	整数型		0
局变_开始位置	整数型
局变_临时_归并	整数型		0
局变_源是临时	逻辑型
n1	整数型
m1	整数型

局变_个数 ＝ 取数组成员数 (参数_数组)
如果真 (局变_个数 ≤ 1)
返回 ()
重定义数组 (局变_临时_归并, 假, 局变_个数)
重定义数组 (局变_游标首, 假, 局变_个数)
重定义数组 (局变_游标尾_, 假, 局变_个数)
如果真 (是否为空 (参数_升序) ＝ 真)
参数_升序 ＝ 真
' ── 第1轮：扫描自然段边界 ──
局变_分段计数 ＝ 1
局变_开始位置 ＝ 1
循环判断首 ()
局变_游标首 [局变_分段计数] ＝ 局变_开始位置
局变_游标尾_ [局变_分段计数] ＝ 子程序_计算尾部 (参数_数组, 局变_游标首 [局变_分段计数])
局变_开始位置 ＝ 局变_游标尾_ [局变_分段计数] ＋ 1
如果 (局变_开始位置 ＞ 局变_个数)
跳出循环 ()
局变_分段计数 ＝ 局变_分段计数 ＋ 1

循环判断尾 (真)
' ── 快速判断 ──
如果 (局变_分段计数 ＝ 1)
如果 (参数_升序 ＝ 真)
返回 ()
数组模块_反转数组_整数型 (参数_数组)
返回 ()

如果 (局变_分段计数 ＝ 局变_个数)
如果 (参数_升序 ＝ 真)
数组模块_反转数组_整数型 (参数_数组)
返回 ()
返回 ()

' 继续归并

' ── 后续轮：两两归并，复用边界 ──
局变_源是临时 ＝ 假
判断循环首 (局变_分段计数 ＞ 1)
' ── 第1个循环：只做合并 ──
变量循环首 (1, 局变_分段计数, 2, n1)
如果 (局变_源是临时 ＝ 假)
子程序_合并4 (参数_数组, 局变_临时_归并, 局变_游标首 [n1], 局变_游标尾_ [n1], 局变_游标首 [n1 ＋ 1], 局变_游标尾_ [n1 ＋ 1])
子程序_合并4 (局变_临时_归并, 参数_数组, 局变_游标首 [n1], 局变_游标尾_ [n1], 局变_游标首 [n1 ＋ 1], 局变_游标尾_ [n1 ＋ 1])

变量循环尾 ()
' ── 第2个循环：只更新边界数组 ──
m1 ＝ 1
变量循环首 (1, 局变_分段计数, 2, n1)
局变_游标首 [m1] ＝ 局变_游标首 [n1]
局变_游标尾_ [m1] ＝ 局变_游标尾_ [n1 ＋ 1]
如果真 (局变_游标尾_ [m1] ＝ 0)
局变_游标尾_ [m1] ＝ 局变_游标尾_ [n1]
m1 ＝ m1 ＋ 1
变量循环尾 ()
' ── 清零：防止下一轮读到旧数据 ──
局变_游标首 [m1] ＝ 0
局变_游标尾_ [m1] ＝ 0
局变_分段计数 ＝ m1 － 1
局变_源是临时 ＝ 取反 (局变_源是临时)
判断循环尾 ()
' ── 最终数据在临时数组，拷回原数组 ──
如果真 (局变_源是临时 ＝ 真)
参数_数组 ＝ 局变_临时_归并

子程序名	返回值类型	公开	备 注
子程序_合并4
参数名	类 型	参考	可空	数组	备 注
参数_源	整数型
参数_目标	整数型
参数_左首	整数型
参数_左尾	整数型
参数_右首	整数型
参数_右尾	整数型

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

' ── 落单：右首=0 或 右尾=0，直接拷贝左段然后返回 ──
如果 (参数_右首 ＝ 0 或 参数_右尾 ＝ 0)
内存拷贝_数组到数组 (参数_目标 [参数_左首], 参数_源 [参数_左首], (参数_左尾 － 参数_左首 ＋ 1) × 4)
返回 ()


' ── 正常合并两段 ──
局变_i ＝ 参数_左首
局变_j ＝ 参数_右首
局变_写 ＝ 参数_左首
循环判断首 ()
如果 (局变_i ＞ 参数_左尾)
跳出循环 ()
如果 (局变_j ＞ 参数_右尾)
跳出循环 ()



如果 (参数_源 [局变_i] ≤ 参数_源 [局变_j])
参数_目标 [局变_写] ＝ 参数_源 [局变_i]
局变_i ＝ 局变_i ＋ 1
参数_目标 [局变_写] ＝ 参数_源 [局变_j]
局变_j ＝ 局变_j ＋ 1
局变_写 ＝ 局变_写 ＋ 1
循环判断尾 (真)
' ── 左段剩余 ──
判断循环首 (局变_i ≤ 参数_左尾)
参数_目标 [局变_写] ＝ 参数_源 [局变_i]
局变_i ＝ 局变_i ＋ 1
局变_写 ＝ 局变_写 ＋ 1
判断循环尾 ()
' ── 右段剩余 ──
判断循环首 (局变_j ≤ 参数_右尾)
参数_目标 [局变_写] ＝ 参数_源 [局变_j]
局变_j ＝ 局变_j ＋ 1
局变_写 ＝ 局变_写 ＋ 1
判断循环尾 ()

子程序名	返回值类型	公开	备 注
子程序_计算尾部	整数型
参数名	类 型	参考	可空	数组	备 注
参数_数组	整数型
参数_游标首	整数型

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

如果 (参数_游标首 ＋ 1 ＞ 取数组成员数 (参数_数组))
返回 (参数_游标首)


变量循环首 (参数_游标首, 取数组成员数 (参数_数组) － 1, 1, n1)
如果 (参数_数组 [n1] ≤ 参数_数组 [n1 ＋ 1])

返回 (n1)

变量循环尾 ()
返回 (取数组成员数 (参数_数组))

.版本 2<br /> <br /> .程序集 程序集8<br /> <br /> .子程序 排序模块_混合归并排序4, , 公开<br /> .参数 参数_数组, 整数型, 数组<br /> .参数 参数_升序, 逻辑型, 可空<br /> .局部变量 局变_个数, 整数型<br /> .局部变量 局变_分段计数, 整数型<br /> .局部变量 局变_游标首, 整数型, , "0"<br /> .局部变量 局变_游标尾_, 整数型, , "0"<br /> .局部变量 局变_开始位置, 整数型<br /> .局部变量 局变_临时_归并, 整数型, , "0"<br /> .局部变量 局变_源是临时, 逻辑型<br /> .局部变量 n1, 整数型<br /> .局部变量 m1, 整数型<br /> <br /> 局变_个数 ＝ 取数组成员数 (参数_数组)<br /> .如果真 (局变_个数 ≤ 1)<br />     返回 ()<br /> .如果真结束<br /> 重定义数组 (局变_临时_归并, 假, 局变_个数)<br /> 重定义数组 (局变_游标首, 假, 局变_个数)<br /> 重定义数组 (局变_游标尾_, 假, 局变_个数)<br /> .如果真 (是否为空 (参数_升序) ＝ 真)<br />     参数_升序 ＝ 真<br /> .如果真结束<br /> ' ── 第1轮：扫描自然段边界 ──<br /> 局变_分段计数 ＝ 1<br /> 局变_开始位置 ＝ 1<br /> .循环判断首 ()<br />     局变_游标首 [局变_分段计数] ＝ 局变_开始位置<br />     局变_游标尾_ [局变_分段计数] ＝ 子程序_计算尾部 (参数_数组, 局变_游标首 [局变_分段计数])<br />     局变_开始位置 ＝ 局变_游标尾_ [局变_分段计数] ＋ 1<br />     .如果 (局变_开始位置 ＞ 局变_个数)<br />         跳出循环 ()<br />     .否则<br />         局变_分段计数 ＝ 局变_分段计数 ＋ 1<br />     .如果结束<br /> <br /> .循环判断尾 (真)<br /> ' ── 快速判断 ──<br /> .如果 (局变_分段计数 ＝ 1)<br />     .如果 (参数_升序 ＝ 真)<br />         返回 ()<br />     .否则<br />         数组模块_反转数组_整数型 (参数_数组)<br />         返回 ()<br />     .如果结束<br /> <br /> .否则<br />     .如果 (局变_分段计数 ＝ 局变_个数)<br />         .如果 (参数_升序 ＝ 真)<br />             数组模块_反转数组_整数型 (参数_数组)<br />             返回 ()<br />         .否则<br />             返回 ()<br />         .如果结束<br /> <br />     .否则<br />         ' 继续归并<br />     .如果结束<br /> <br /> .如果结束<br /> ' ── 后续轮：两两归并，复用边界 ──<br /> 局变_源是临时 ＝ 假<br /> .判断循环首 (局变_分段计数 ＞ 1)<br />     ' ── 第1个循环：只做合并 ──<br />     .变量循环首 (1, 局变_分段计数, 2, n1)<br />         .如果 (局变_源是临时 ＝ 假)<br />             子程序_合并4 (参数_数组, 局变_临时_归并, 局变_游标首 [n1], 局变_游标尾_ [n1], 局变_游标首 [n1 ＋ 1], 局变_游标尾_ [n1 ＋ 1])<br />         .否则<br />             子程序_合并4 (局变_临时_归并, 参数_数组, 局变_游标首 [n1], 局变_游标尾_ [n1], 局变_游标首 [n1 ＋ 1], 局变_游标尾_ [n1 ＋ 1])<br />         .如果结束<br /> <br />     .变量循环尾 ()<br /> <br />     ' ── 第2个循环：只更新边界数组 ──<br />     m1 ＝ 1<br />     .变量循环首 (1, 局变_分段计数, 2, n1)<br />         局变_游标首 [m1] ＝ 局变_游标首 [n1]<br />         局变_游标尾_ [m1] ＝ 局变_游标尾_ [n1 ＋ 1]<br />         .如果真 (局变_游标尾_ [m1] ＝ 0)<br />             局变_游标尾_ [m1] ＝ 局变_游标尾_ [n1]<br />         .如果真结束<br />         m1 ＝ m1 ＋ 1<br />     .变量循环尾 ()<br /> <br />     ' ── 清零：防止下一轮读到旧数据 ──<br />     局变_游标首 [m1] ＝ 0<br />     局变_游标尾_ [m1] ＝ 0<br />     局变_分段计数 ＝ m1 － 1<br />     局变_源是临时 ＝ 取反 (局变_源是临时)<br /> .判断循环尾 ()<br /> ' ── 最终数据在临时数组，拷回原数组 ──<br /> .如果真 (局变_源是临时 ＝ 真)<br />     参数_数组 ＝ 局变_临时_归并<br /> .如果真结束<br /> <br /> <br /> .子程序 子程序_合并4<br /> .参数 参数_源, 整数型, 数组<br /> .参数 参数_目标, 整数型, 数组<br /> .参数 参数_左首, 整数型<br /> .参数 参数_左尾, 整数型<br /> .参数 参数_右首, 整数型<br /> .参数 参数_右尾, 整数型<br /> .局部变量 局变_i, 整数型<br /> .局部变量 局变_j, 整数型<br /> .局部变量 局变_写, 整数型<br /> <br /> ' ── 落单：右首=0 或 右尾=0，直接拷贝左段然后返回 ──<br /> .如果 (参数_右首 ＝ 0 或 参数_右尾 ＝ 0)<br />     内存拷贝_数组到数组 (参数_目标 [参数_左首], 参数_源 [参数_左首], (参数_左尾 － 参数_左首 ＋ 1) × 4)<br />     返回 ()<br /> .否则<br /> <br /> .如果结束<br /> ' ── 正常合并两段 ──<br /> 局变_i ＝ 参数_左首<br /> 局变_j ＝ 参数_右首<br /> 局变_写 ＝ 参数_左首<br /> .循环判断首 ()<br />     .如果 (局变_i ＞ 参数_左尾)<br />         跳出循环 ()<br />     .否则<br />         .如果 (局变_j ＞ 参数_右尾)<br />             跳出循环 ()<br />         .否则<br /> <br />         .如果结束<br /> <br />     .如果结束<br />     .如果 (参数_源 [局变_i] ≤ 参数_源 [局变_j])<br />         参数_目标 [局变_写] ＝ 参数_源 [局变_i]<br />         局变_i ＝ 局变_i ＋ 1<br />     .否则<br />         参数_目标 [局变_写] ＝ 参数_源 [局变_j]<br />         局变_j ＝ 局变_j ＋ 1<br />     .如果结束<br />     局变_写 ＝ 局变_写 ＋ 1<br /> .循环判断尾 (真)<br /> ' ── 左段剩余 ──<br /> .判断循环首 (局变_i ≤ 参数_左尾)<br />     参数_目标 [局变_写] ＝ 参数_源 [局变_i]<br />     局变_i ＝ 局变_i ＋ 1<br />     局变_写 ＝ 局变_写 ＋ 1<br /> .判断循环尾 ()<br /> ' ── 右段剩余 ──<br /> .判断循环首 (局变_j ≤ 参数_右尾)<br />     参数_目标 [局变_写] ＝ 参数_源 [局变_j]<br />     局变_j ＝ 局变_j ＋ 1<br />     局变_写 ＝ 局变_写 ＋ 1<br /> .判断循环尾 ()<br /> <br /> .子程序 子程序_计算尾部, 整数型<br /> .参数 参数_数组, 整数型, 数组<br /> .参数 参数_游标首, 整数型<br /> .局部变量 n1, 整数型<br /> <br /> .如果 (参数_游标首 ＋ 1 ＞ 取数组成员数 (参数_数组))<br />     返回 (参数_游标首)<br /> .否则<br /> <br /> .如果结束<br /> .变量循环首 (参数_游标首, 取数组成员数 (参数_数组) － 1, 1, n1)<br />     .如果 (参数_数组 [n1] ≤ 参数_数组 [n1 ＋ 1])<br /> <br />     .否则<br />         返回 (n1)<br />     .如果结束<br /> <br /> .变量循环尾 ()<br /> 返回 (取数组成员数 (参数_数组))

  

DLL命令名	返回值类型	公开	备 注
内存拷贝_数组到数组
DLL库文件名:
kernel32.dll
在DLL库中对应命令名:
RtlMoveMemory
参数名	类 型	传址	数组	备 注
目标首元素	整数型			, 传目标数组[1]等，自动得到jz
源首元素	整数型			, 传源数组[1]等，自动得到jz
长度	整数型			, 拷贝的字节数

.版本 2<br /> <br /> .DLL命令 内存拷贝_数组到数组, , "kernel32.dll", "RtlMoveMemory"<br />     .参数 目标首元素, 整数型, 传址, , 传目标数组[1]等，自动得到jz<br />     .参数 源首元素, 整数型, 传址, , 传源数组[1]等，自动得到jz<br />     .参数 长度, 整数型, , , 拷贝的字节数

ttggnn

感谢分享

杨明煜

真值得学习，感谢！......

卡卡1111

        感谢分享，很给力！~

bianyuan456

已经顶贴，感谢您对论坛的支持！

kyo9766

可以学习一下原理，感谢分享

1184798949

感谢分享

myface

支持一下