Push_swap：在两个可旋转堆栈上使用一组有限的指令对给定值进行排序的最有效方法是什么？

这是您已经拒绝的 https://stackoverflow.com/a/38165541/585411 的变体。但希望你能理解我对如何更好地进行自下而上的合并排序的解释。

运行是按排序顺序排列的一组数字。起初，你有很多次运行，大概大多数都是小长度的。当你在堆栈中运行一次时，你就完成了。A

首先，当底部元素是顶部时，继续向后旋转。这会将运行的开始位置在 的顶部。A<=A

接下来，我们需要在 和 之间平均分配运行。我们的做法是经历一次，寻找运行。第一次运行在 的底部，第二次运行在 的底部，依此类推。（放置在底部只需要，直到运行完成。放在底部意味着 .）ABAABAraBpbrb

一旦我们拆分了运行，我们要么只是在底部放置一个运行，并且比 多一个运行，要么我们只是在底部放置一个运行，并且它们具有相同的运行次数。AABB

现在开始合并运行，同时继续在 和 之间切换。每次合并时，如果您合并到，则最终再运行一次。如果合并到，则运行次数相同。ABAAB

将运行合并到如下所示：B

if top of A < top of B:
    pb
rb
while bottom of B <= top of B:
    if top of A < top of B:
        pb
    rb
while bottom of B <= top of A:
    pb
    rb

将运行合并到与此类似，只是颠倒了堆栈的角色。A

继续，直到为空。此时有 0 次运行，而有一次。这意味着已排序。BBAA

该算法将进行比较。O(n log(n))

---

自从我第一次回答这个问题以来，这个问题已经发生了很大变化，所以这里有一些优化的想法。

首先，在拆分时，我们可以做得更好，而不仅仅是处理 run to 和 。具体来说，我们可以将上升的运行放在 的底部，并将下降的运行推到（使它们上升）。偶尔会延长跑步时间。这些操作可以交错进行，因此，例如，我们可以处理然后将它们合并，从而使用 11 个操作对其进行排序。（这可能不是最佳的，但它给了你一个想法。如果你对此很聪明，你可能会从两堆的平均运行长度开始，大约是 4 个（也许更好）。在拆分过程中，您可以提前查看几条指令，以弄清楚如何有效地完成更长的运行。（如果您在 4 次运行中有 500 个元素，那就是 125 次运行。合并排序过程现在应该能够在 7 次传递中完成。ABABsa5 2 3 1 4pb ra ra pb rapa ra ra ra pa ra

我们是否已经找到了潜在的优化？当然不是。

当我们开始合并传递时，我们现在有不均匀的运行次数和不均匀数量的元素。我们将合并成对的运行，将它们放在某个地方，再次合并成对，将它们放在某个地方，等等。完成传递后，我们希望有两件事是正确的：

1. 两个堆栈中的平均运行长度应大致相同（合并相似长度的运行效率更高）。
2. 我们希望使用尽可能少的操作。由于合并到执行操作，因此我们把合并放在哪里很重要。nm2n+m

我们可以使用动态规划来解决这两个约束。为此，我们使用以下信息构建数据结构：

by the number of merged runs created:
    by the number of runs put in `A`
        by the number of elements put in `A`
            minimal number of required steps
            last stack merged into

然后，我们可以查看创建运行次数最多的部分，并找出使平均运行大小尽可能接近的原因。然后回过头来弄清楚哪个合并序列以最少的步数到达那里。然后我们可以计算出我们采取了哪些步骤的顺序，以及我们在哪里结束。

当你把所有这些放在一起时，我怀疑你只能用 5000 个步骤对 5000 个元素进行排序。但是，如果您不能将其平均降低到6000以下，我会感到惊讶。

一旦你拥有了所有这些，你就可以开始寻找更好的优化。（“我们不在乎需要多少分析才能产生动作”是邀请我们花费无限的精力进行优化。

问题需要编辑。该练习称为“推送交换”，这是针对 42 学校（未经认证的学校）学生的项目。该项目的第二部分称为“检查器”，用于验证“推送交换”的结果。

以下是描述推送交换质询的链接 |项目。剧透警告：它还包括作者对 100 和 500 数字的方法，因此您可能希望在 3 和 5 数字示例之后停止阅读。

https://medium.com/@jamierobertdawson/push-swap-the-least-amount-of-moves-with-two-stacks-d1e76a71789a

术语堆栈被错误地用于描述容器 a 和 b（可能是法语到英语的翻译问题），因为交换和轮换不是本机堆栈操作。常见的实现使用循环双向链表。

Push Swap：输入一组要放入 A 中的整数，并生成导致 A 排序的 11 个操作的列表。其他变量和数组可用于生成操作列表。一些网站在整数集中没有提到重复项。如果存在重复项，我会假设一个稳定的排序，其中重复项将保持其原始顺序。否则，如果要寻求最佳解决方案，则需要测试所有重复项的排列。

checker：验证 push swap 的结果。

这两个程序都需要验证输入并产生结果。

一个网站列出了推送交换的评分方式。

required: sort   3 numbers with <=     3 operations
required: sort   5 numbers with <=    12 operations
scored:   sort 100 numbers with <=   700 operations   max score
                                     900 operations
                                    1100 operations
                                    1300 operations
                                    1500 operations   min score
scored:   sort 500 numbers with <=  5500 operations   max score
                                    7000 operations
                                    8500 operations
                                   10000 operations
                                   11500 operations   min score

下面给出了算法中允许生成操作列表的概念。第一步是将 a 中的值转换为等级（这些值永远不会再次使用）。如果是重复项，请在转换为等级时使用重复项的顺序（稳定排序），因此没有重复的等级。排名的值是排名在排序数组中所属的位置：

    for(i = 0; i < n; i++)
        sorted[rank[i]] = rank[i].

例如，值 {-2 3 11 9 -5} 将转换为 {1 2 4 3 0}：-2 属于 sorted[1]，3 属于 sorted[2]，...、-5 属于 sorted[0]。对于允许重复的稳定排序，值 {7 5 5 1 5} 将转换为 {4 1 2 0 3}。

如果 a 有 3 个等级，则等级有 6 种排列，最多需要 2 次运算才能对 a 进行排序：

{0 1 2} : already sorted
{0 2 1} : sa ra
{1 0 2} : sa
{1 2 0} : rra
{2 0 1} : ra
{2 1 0} : sa rra

对于 5 个等级，可以使用 2 个操作将 2 个移动到 b，剩下的 3 个在排序中最多 2 个操作，留下至少 8 个操作将 2 个等级从 b 插入到 a 中，最终得到排序的 a。只有 20 种可能的方法可以将 2 个等级从 b 移动到 a，小到足以创建一个包含 20 个优化操作集的表。

对于 100 和 500 号码，有多种策略。

剧情透露：

Youtube 视频显示 n=100 时有 510 次操作，n=500 时显示 3750 次操作。

https://www.youtube.com/watch?v=2aMrmWOgLvU

描述转换为英文：

Initial stage :
 - parse parameters
 - Creation of a stack A which is a circular doubly linked list (last.next = first; first.prec = last
 - Addition in the struct of a rank component, integer from 1 to n.
This will be much more practical later.
Phase 1 :
 - Split the list into 3 (modifiable parameter in the .h).
 - Push the 2 smallest thirds into stack B and do a pre-sort. do ra with others
 - Repeat the operation until there are only 3 numbers left in stack A.
 - Sort these 3 numbers with a specific algo (2 operations maximum)
Phase2:
 (Only the ra/rra/rb/rrb commands are used. sa and sb are not used in this phase)
 - Swipe B and look for the number that will take the fewest moves to be pushed into A.
 There are each time 4 ways to bring a number from B to A: ra+rb, ra+rrb, rra+rb, rra+rrb. We are looking for the mini between these 4 ways.
 - Then perform the operation.
 - Repeat the operation until empty B.
Phase 3: If necessary rot stack A to finalize the correct order. The shorter between ra or rra.
The optimization comes from the fact of the maximum use of the double rotations rr and rrr

解释：

Replace all values in a by rank.
For n = 100, a 3 way split is done:
ranks 0 to 32 are moved to the bottom of b,
ranks 33 to 65 are moved to the top of b,
leaving ranks 66 to 99 in a.
I'm not sure what is meant by "pre-sort" (top | bottom split in b?).
Ranks 66 to 99 in a are sorted, using b as needed.
Ranks from b are then inserted into a using fewest rotates.
For n = 500, a 7 way split is done:
Ranks 0 to 71 moved to bottom of b, 72 to 142 to top of b, which
will end up in the middle of b after other ranks moved to b.
Ranks 143 to 214 to bottom of b, 215 to 285 to top of b.
Ranks 286 to 357 to bottom of b, 358 to 428 to top of b.
Leaving ranks 429 to 499 in a.
The largest ranks in b are at the outer edges, smallest in the middle,
since the larger ranks are moved into sorted a before smaller ranks.
Ranks in a are sorted, then ranks from b moved into a using fewest rotates.