什么是这个问题或解决方案算法的正确名称？

Question

我有一个二维数组，其中包含唯一的整数 - 这表示一个物理容器与行/列 - 在每个位置有一个小瓶。

我知道应该在数组中的整数以及它们应该位于何处。

但是，我的数组在错误的位置上可能有很多/所有唯一的整数。

我现在需要排序数组 - 但是这映射到一个物理过程，因此我真的想减少由于潜在的人为错误而涉及的排序步骤的数量。

这只是一个普通的排序吗？或者这种情况下是否有更具体的名称？有没有众所周知的解决方案

我的同事建议只是用[2] [1]类型的指令创建一个swap [1] [1]的列表，这似乎是合理的，但是如果交换次序很重要，我不能完全理解。

感谢所有帮助。

Answer 1

如果你真的可以看出来，只要看一下瓶子的属性，最简单的方法就是把第一瓶放在错误的地方，然后把它放在它所属的地方，把它放在适当的地方等等，直到你碰巧得到了你最初制造一个“洞”的小瓶。然后重复。

由于您最多一次取出每个小瓶，并且只有在错误的地方，我认为这是关于物理运动的最佳选择。

Answer 2

排序算法分析的数量为比较和交换所需的数量。由于对于操作人员来说，交换的成本远高于比较的成本，因此您需要一种2D排序，以尽量减少需要的交换的数量。

Answer 3

“如果互换顺序很重要，我不能完全理解。”

我一般是的，它是。举一个简单的例子，考虑3个元素的起始列表，X Y Z。

“用2交换1，用3交换2”的结果是Y Z X。

“交换2与3，然后1与2”的结果是Z X Y。

您提出的掉期清单可能（最多）为每个不合适的元素1，并且将该元素与正确位置的任何元素进行交换。因此，举例来说，您可能会将[0][0]与其所属的任何地方互换。除非它所属的地方碰巧包含属于[0][0]的元素，否则您的下一个交换可能是[0][0]，而即所属的地方。所以当然，掉期的顺序很重要 - 第二次掉期只是正确的，因为第一次掉期已经发生，并且将一些特定元素转移到[0][0]。

但是，如果两个连续掉期不相交，那么您可以颠倒它们的顺序：(1 2)(3 4)相当于(3 4)(1 2)，其中(x y)是“swap x with y”的数学表示法。

这是一个定理，任何置换都可以写成一组不相交的循环。除了您选择首先列出的循环中的哪些元素以及循环列出的顺序之外，循环中的这种分解是唯一的，这两种循环与结果无关。符号(1 2 3)的意思是“将1移动到2，2到3和3移动到1”，并且是3个周期。它与(2 3 1)完全一样，但与(1 3 2)不同。

这取决于你的人类操作工作方式，它可能更有效率地执行n循环而不是等价的n次交换。所以一旦你知道如何对你的数组进行排序（也就是说，你知道必须对它进行排列才能使其排列顺序），最好的办法就是生成这个分解。