arrays - 通过交换对二维数组进行排序的算法

Question

对于一维数组，可以通过冒泡排序轻松实现交换排序，例如:

5 4 9 8 7 1 6 3 2 10

将需要 25 次交换才能输出

1 2 3 4 5 6 7 8 9 10

---

然而，在二维数组中，我们有这样的东西。

4 2 3
1 8 5
7 9 6

项目可以垂直和水平交换，但不能沿对角线交换:

• 交换 4 和 1
• 交换 8 和 5
• 交换 8 和 6
• 交换 9 和 8

这成为排序数组:

1 2 3
4 5 6
7 8 9

我正在寻找一种可以有效实现这一目标的算法(最大限度地减少交换次数)。此问题可能类似于 15 puzzle ，尽管它要简单得多，因为每个项目都可以与相邻项目交换，而不仅仅是与空图 block 交换。

Answer 1

在一维数组中，冒泡排序不仅永远交换相邻元素，而且永远比较相邻元素。

没有什么类似的东西真正适用于二维数组，因为你无法检测到它

1 2 4
3 5 6
7 8 9

乱序(因为您不能直接比较不相邻的 3 和 4)。

如果我们说您可以检查和比较任意 元素，但更新元素的唯一方法是将它与其相邻元素之一交换，那么最好的方法是从完全开始找出每个元素需要在哪里结束(例如，通过将元素复制到常规数组并应用标准排序算法)，然后才执行必要的交换以将元素移动到它们的目的地。