这是一道作业题(sorry，我知道这些都是不受欢迎的)，但实际上我和老师都不知道如何有效地解决它，所以我想把它放在这里，看看SO上的高手是否可以帮助我们。
给出了一个未指定大小的数组，其中包含随机数。它必须按升序排列。每个元素都可以移动到相邻的空白空间，或者移动到相邻的较大元素的顶部。我需要编写一个方法来返回对给定数组进行排序所需的最少移动次数。
这个问题被标记为“可选”，因为老师意识到这个问题太难了，但我很好奇它是如何解决的。对任何大小的数组的任何建议(对于我所关心的，它可以是长度为 3 的数组)表示赞赏。
编辑:感谢您指出这还不清楚。我正在使用数组来表示假设的现实世界情况。让我们以硬币为例:它们都排成一排放在 table 上，只能放入指定数量的“空格”。但是它们可以放在相邻的较大硬币之上，或者滑动到相邻的空白空间(已被可能移动到一堆顶部的硬币腾出)。
最佳答案
我决定通过一些假设/更改来检查这个问题，因为这对我来说是一个更有趣的问题:
1) 您可以从堆的任何部分向左或向右移动元素。
2) 你可以把一个元素堆成一堆，不管它是大是小还是一样大。
3) 无论您如何遍历堆栈，只要您从未在较小的数字之前遇到较大的数字，就认为该数组已排序。所以 _ 11 2 3 已排序，但 _ _ 12 3 未排序，因为您可以将 2 解释为在 1 之前。
这导致了一个非常有趣的问题，尽管有这个公理:
公理 A:您移动的顺序是无关紧要的，可以以任何方式重新安排以仍然获得相同的最终结果。
Axiom Ab:如果数组中没有重复项，则只需将每个元素移向其最终位置即可。
特别是，我制定了一种策略，希望您仅通过局部检查就可以解决它，而无需递归/回溯，但我已经证明这是徒劳的，稍后会展示。
我的策略是:
1) 从左到右寻找翻转方向错误的对(较大的数字在较小的数字之前)。
2a) 当你找到一个时，如果有一个空点或一堆右边的值可以立即填充，将它向左移动直到它填满它。
2b) 否则，将左边的值向右移动一个。这会造成您有一堆无关数字的情况 - 首先，在向下比较之前，根据 1) 的逻辑将您向右移动的值与其新右侧的值进行比较。
2bii) 以与成对比较相同的方式对待向下比较 - 如果它可以容纳一个空点或堆栈，则将较低的值向左移动，否则将较高的值向右移动并继续。
例子:
1231 -> 我们向左移动 1b 因为它适合堆栈。 11 2 3 _
1321 -> 我们将 3 右移，因为 2 不适合空位/堆栈。我们将 1b 向左移动两次，因为它适合空位/适合堆栈，然后我们将 3 向右移动，因为 2 不适合空位/适合堆栈。 1 1 2 3
1132 -> 我们将 3 向右移动，因为 2 不能向左移动。我们将 2 向左移动，因为它适合一个空位。 1 1 2 3
2311 -> 我们将 3 向右移动，因为 1a 不能向左移动。我们将 1b 向左移动两次，因为它适合一个空位。我们向左移动 1a 因为它会堆叠。我们将 2 向右移动，因为 1a1b 不能向左移动。我们将 1a2b 向左移动，因为它将填补一个空白点。 11 2 3 _
但是，我们遇到了这两个起始数组的问题:
23411 10 步最优，2r 3r 4r 1al*3 1bl*4 得到 11 2 3 4 _。
23111 9 步最优，2r*3 3r*3 1bl 1cl*2 使 _ _ 111 2 3 - 与 23411 策略相反!我们少移动 1 而多移动 23，因为有更多的 1，所以我们尽可能少地移动它们。
这表明我们不能仅仅通过简单的局部比较来解决这个新问题。
我仍在思考这个问题，它以一种有趣的方式看起来并不平凡，我希望你们中的一些人喜欢和我一起思考这个问题:)
关于java - 使用简单的数组通过堆叠对数字进行排序？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15891424/