基于受限指令集的双栈选择排序优化方案问询

背景与问题 #

基于栈A、B及以下受限指令实现排序，目标优化选择排序、最小化指令执行次数：

• sa (交换栈A顶部两个元素)
• sb (交换栈B顶部两个元素)
• ss (同时执行sa和sb)
• pa (将栈B顶部元素移至栈A顶部)
• pb (将栈A顶部元素移至栈B顶部)
• ra (栈A所有元素上移一位，顶部元素移至栈底)
• rb (栈B所有元素上移一位，顶部元素移至栈底)
• rr (同时执行ra和rb)
• rra (栈A所有元素下移一位，栈底元素移至顶部)
• rrb (栈B所有元素下移一位，栈底元素移至顶部)
• rrr (同时执行rra和rrb)

原算法为每次找栈A全局最小元素，通过ra/rra移至栈顶后pb到B，重复后pa回A，但随机元素场景下效率极低。现需调整算法，将栈A预分区为顶部25%最小元素、中间50%最大元素、底部25%次小元素，再执行排序以减少指令数。

优化方案 #

一、预统计与分组 #

1. 遍历栈A一次，记录所有元素值，计算两个阈值：
   • S_max：最小25%元素的最大值（第25百分位）
   • M_max：次小25%元素的最大值（第75百分位）
2. 划分三个元素组：
   • S组：≤S_max（最小25%）
   • M组：>S_max且≤M_max（次小25%）
   • L组：>M_max（最大50%）

二、构建目标分区结构 #

通过双栈配合，将栈A调整为栈顶→栈底：S组 → L组 → M组的结构：

1. 分离S组到栈B：
   • 遍历栈A，对每个元素：
     • 若为S组：执行pb移至栈B
     • 若为M/L组：执行ra留在栈A
   • 完成后：栈B=S组，栈A=M+L组混合
2. 分离M组到栈B：
   • 遍历栈A，对每个元素：
     • 若为M组：执行pb移至栈B（此时栈B结构为栈底→栈顶：S组 → M组）
     • 若为L组：执行ra留在栈A
   • 完成后：栈B=S+M组，栈A=L组
3. 重组栈A为目标结构：
   • 执行pa操作len(M)次，将栈B中的M组移回栈A（此时栈A栈底→栈顶：M组）
   • 执行pa操作len(S)次，将栈B中的S组移回栈A（此时栈A栈底→栈顶：M组 → L组 → S组，即栈顶→栈底为S组 → L组 → M组）

三、分区后的排序流程 #

利用分区后的局部有序性，减少旋转操作次数：

1. 排序S组（栈顶）：
   • 在栈A内部对S组排序：用sa交换相邻元素，配合少量ra/rra调整顺序，将S组从小到大排列在栈顶
   • 依次执行pb将排序后的S组移至栈B（栈B此时栈底→栈顶：最小元素 → S组最大元素）
2. 排序L组（中间）：
   • 遍历栈A中的L组，每次找到L组内的最小元素：
     • 对比ra和rra的步数，选择更少的操作将该元素移至栈顶
     • 执行pb将元素移至栈B（放在S组下方）
   • 重复直至L组全部移至栈B
3. 排序M组（栈底）：
   • 栈A中仅剩M组，执行rra将栈底的M元素移至栈顶（因M组在底部，rra步数远少于ra）
   • 排序后依次执行pb移至栈B
4. 最终回移：
   • 栈B中元素已按从小到大排序（栈底→栈顶：最小 → 最大），执行pa操作将所有元素移回栈A，完成排序

四、指令优化技巧 #

• 批量操作优先：移动多个元素时，连续执行ra/rra而非分散操作
• 合并指令复用：同时需要旋转A和B时，用rr/rrr替代ra+rb/rra+rrb，减少指令总数
• 跳过无效操作：栈元素数量<2时不执行sa/sb；栈为空时不执行pa/pb等

内容的提问来源于stack exchange，提问作者Saad Out03