algorithm - 如何使用相邻元素的最小交换对数组进行排序

Question

我有一个算法可以解决教授必须根据学生的类(class)分数对学生进行排序的问题，例如 1 表示好，0 表示差。在最少数量的交换中，只有相邻的学生可以交换。例如，如果学生按顺序 [0,1,0,1] 给出，则只需要一次交换即可完成 [0,0,1,1] 或 [0,0,0,0,1,1, 1,1] 不需要交换。

从问题描述中我立即知道这是我们可以在归并排序中找到的经典最小相邻交换问题或计数倒置问题。我尝试了自己的算法以及列出的算法 here或 this site但没有人通过所有测试。

当我尝试以相反顺序对数组进行排序时，通过了最多的测试用例。我还尝试根据数组的第一个元素是 0 还是 1 按顺序对数组进行排序。例如，如果第一个元素是 1，那么我应该按降序对数组进行排序，否则按升序对数组进行排序，因为学生可以在任何分组中，仍然没有工作。有些测试用例总是失败。问题是当我按升序对它进行排序时，在反向排序的情况下失败的一个测试用例与其他一些但不是全部通过了。所以我不知道我做错了什么。

Answer 1

在我看来，当涉及到 0 和 1 的数组时，术语“排序”有点夸张了。您可以简单地计算 O(n) 中的 0 和 1 并生成输出。

为了解决“最小交换”部分，我构建了一个玩具示例；我想到了两个想法。所以，例子。我们正在对学生进行分类...f:

a b c d e f
0 1 0 0 1 1

a c d b e f
0 0 0 1 1 1

如您所见，这里没有太多的排序。三个 0，三个 1。

首先，我将其框定为 edit distance问题。 IE。您需要仅使用“交换”操作将 abcdef 转换为 acdbef。但是，您首先是如何想到 acdbef 的呢？我在这里的假设是，您只需要将 0 和 1 拖到数组的相对两侧而不打乱它们的顺序。例如

        A     B     C     D
0 0 ... 0 ... 1 ... 0 ... 1 ... 1 1

0 0 0 0         ...         1 1 1 1
    A C                     B D

我不能 100% 确定它是否有效以及是否真的能为您带来最少的交换。但这似乎是合理的——你为什么要花额外的钱换 e。 G。 A和C？

关于应该将 0 放在最前面还是最后 - 我认为两次运行相同的算法并比较交换量没有问题。

关于如何找到交换量，甚至交换顺序 - 从编辑距离的角度考虑可以帮助您解决后者。仅查找交换数量也可以是编辑距离的一种简化形式。或者也许更简单的东西 - e。 G。找到最接近其“簇”的某物(0 或 1)，然后移动它。然后重复直到数组排序。