algorithm - 通过使用最小交换交换相邻元素对序列进行排序

Question

我们有一个未排序的 N 数序列(1, 2, 3, 4, ... N)。我们可以通过按特定顺序交换相邻元素来对整个序列进行排序。给定一个序列，我如何计算对序列进行排序所需的最小可能交换。

例如，考虑序列 {4, 2, 5, 3, 1}。

最好的排序方法是按以下顺序使用 7 个交换

1. 交换 3、1:{4、2、5、1、3}
2. 交换 5、1:{4、2、1、5、3}
3. 交换 4、2:{2、4、1、5、3}
4. 交换 4、1:{2、1、4、5、3}
5. 交换 2、1:{1、2、4、5、3}
6. 交换 5、3:{1、2、4、3、5}
7. 交换 3、4:{1、2、3、4、5}

贪心算法并没有被证明是富有成果的。一个反例很容易构造。接近解决方案的下一个明显选择是动态规划。

假设我们有一个未排序的序列:{A1, A2, ...Ai, A(i+1), ..., An}。我们知道对序列 {Ai, A(i+1), ..., An} 进行排序所需的最小交换次数是 Min[Ai, A(i+1), ..., An}。问题是找到 Min[A(i-1), Ai, ..., An]。

好吧，我脑海中浮现的第一个想法就是添加将 A(i-1) 放入已排序序列 {Ai, ..., An} 中正确位置所需的步数。这行得通:问题中给出的示例已使用完全相同的方法解决。

但我无法证明这个解决方案的有效性。我经常是这种情况。当我认为我已经解决了问题时，我能做的最好的事情就是获得一个“直观”的证明。我在读高中，没有接受过算法方面的正规培训。我这样做纯粹是出于兴趣。

是否有严密的数学符号可以将这个问题转化为形式化证明？这个符号可以扩展到其他问题吗？如何？如果它能以高中生可以理解的形式呈现，我将不胜感激。

Answer 1

这是一个经典的算法问题。最小交换次数等于数组中的反转次数。如果我们有索引 i和索引j这样 a_i> a_j 和 i < j那么这就是所谓的反转。让我们来证明这个说法!途中我需要一些引理:

引理 1:如果两个相邻元素没有反转，则数组被排序。
证明: 假设没有两个相邻元素形成反转。这意味着对于区间 [0, n-1] 中的所有 i，a_i <= a_i+1。作为<=是可传递的，这意味着数组已排序。

引理 2:两个相邻元素的单次交换将使数组中的反转总数最多减少 1。
证明:当我们交换两个相邻元素 a_i 和 a_i+1 时，它们相对于数组中所有其他元素的相对位置将保持不变。那就是对于所有在 a_i+1 之后的元素，它们仍然在 a_i+1 之后，对于 a_i 之前的所有元素, 它们仍然在 a_i 之前。这也意味着，如果 a_i 或 a_i+1 与元素 a_j 形成反演，那么它们仍将与元素形成反演交换后的它。因此，如果我们交换 a_i 和 a_i+1，我们只会影响这两个元素曾经形成的反转。由于两个元素最多只能参与一次反演，我们也证明了引理。

引理 3:我们需要至少对相邻元素执行 NI 次交换才能对数组进行排序，其中 NI 是数组中的反转次数
证明: 在有序数组中没有反转。同样根据引理 2，单次交换最多可以将反转次数减少一次。因此，我们至少需要执行与反转次数一样多的交换。

引理 4:我们总是可以对数组进行 NI 交换相邻元素的排序，其中 NI 是数组中的反转次数。
证明: 如果我们假设在我们的数组中没有两个相邻元素的反转，那么根据引理 1，数组将被排序，我们就完成了。
否则至少有一对相邻元素形成反转。我们可以交换它们，从而将反转的总数减少一次。我们可以继续执行此操作恰好 NI 次。

现在我已经从答案的开头证明了我的说法。

剩下的唯一问题是如何计算给定数组中的反转次数。您可以使用合并排序的轻微修改来做到这一点，您可以在合并阶段累积反转。你可以看看this answer有关如何实现它的详细信息。算法的整体复杂度为O(n*log(n)) .