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

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

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

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

贪婪算法并没有取得成果。一个反例很容易构建。解决方案的下一个明显选择是动态编程。

假设我们有一个未排序的序列：{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}中的正确位置所需的步骤数。这行得通：问题中给出的示例已使用完全相同的方法解决。

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

是否存在严格的数学符号可以将该问题转化为形式并得到正式证明？可以将此表示法扩展到其他问题吗？怎么样？如果能以高中生可以理解的形式呈现它，我将不胜感激。

这是一个经典的算法问题。如果交换的最小数量等于数组中的反转数量。如果我们的索引i和索引j使得a i > a j且i

<j，则这称为反转。让我们证明这一说法！在此过程中，我将需要一些引理：

如果没有两个元素的求逆，则对数组进行排序。

让我们假设没有两个相邻的元素构成一个反转。这意味着在区间[0，n-1]中，所有i 的i <= i i +

1。作为<=可传递的，这意味着将对数组进行排序。

两个相邻元素的一次交换最多会将数组中的反转总数减少1。

当我们交换两个相邻元素a i和i + 1时，它们相对于所有其他元素的相对位置在数组中将保持不变。也就是说，对于所有在i +

1之后的元素，它们仍将在i + 1之后，对于在i之前的所有元素，它们仍将在a i之前。这也意味着，如果一个i或一个i + 1与一个元素a

j形成一个倒数，那么它们在交换之后仍将与其形成一个倒数。因此，如果我们交换一个i和i +

1我们将仅影响这两个元素形成的反转。由于两个元素可能参与的反演次数不超过一个，因此我们也证明了引理。

我们至少需要对相邻元素进行NI交换才能对数组进行排序，其中NI是数组中反转的数量。

在排序数组中没有反转。同样根据引理2，单个交换最多可以减少一次反转。因此，我们至少需要执行与反转次数一样多的交换。

我们总是可以对执行相邻元素的NI交换的数组进行排序，就像在NI上方一样，数组中的反转次数也是如此。

如果我们假设数组中不存在两个相邻元素的求逆，则根据引理1，将对数组进行排序并完成。

否则，至少有一对相邻的元素构成一个反演。我们可以交换它们，从而将反演的总数减少一次。我们可以继续准确执行NI次此操作。

现在，我已经从答案的开头证明了我的观点。

剩下的唯一问题是如何计算给定数组中的反转次数。您可以使用对合并排序的略微修改来做到这一点，在合并阶段中累积反转。您可以查看此答案)以获取有关如何实现该功能的详细信息。该算法的整体复杂度为O(n*log(n))。