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

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

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

有没有严格的数学符号可以将这个问题转化为形式化证明？这个表示法可以推广到其他问题吗？如何？如果它能以高中生可以理解的形式呈现，我将不胜感激。

This is a classical algorithm problem. The minimum number of swaps is equal to the number of inversions in the array. If we have index i and index j such that a_i > a_j and i < j then this is called an inversion. Let's prove this statement! I will need a few lemmas on the way:

Lemma 1: If there is no inversion of two adjacent elements then the array is sorted.
Proof: Let's assume that no two adjacent elements form an inversion. This means that a_i <= a_i+1 for all i in the interval [0, n-1]. As <= is transitive this will mean that the array is sorted.

Lemma 2: A single swap of two adjacent elements will reduce the total number of inversions in the array by at most 1.
Proof: when we swap two adjacent elements a_i and a_i+1 their relative position with respect to all the other elements in the array will remain unchanged. That is for all elements that were after a_i+1, they will still be after a_i+1 and for all elements before a_i, they will still be before the a_i. This also means that if a_i or a_i+1 formed an inversion with an element a_j then, they will still form an inversion with it after the swap. Therefor if we swap a_i and a_i+1 we will affect only inversions that these two elements used to form. As two elements may participate in no more than one inversion we have also proved the lemma.

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

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

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

剩下的唯一问题是如何计算给定数组中的反转次数。您可以通过稍微修改合并排序来实现这一点，在合并阶段累积反转。你可以看看这个答案有关如何实施的详细信息。算法的总体复杂度为O(n*log(n)).