我们有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使得ai> aj且i
引理1:如果相邻元素的两个没有反转，则对数组进行排序。
证明:假设没有两个相邻的元素构成一个反转。这意味着在间隔[0，n-1]中，所有i的ai <=是可传递的，这意味着将对数组进行排序。
引理2:一次两个相邻元素的交换将使数组中反转的总数最多减少1。
证明:，当我们交换两个相邻元素ai和ai + 1时，它们相对于数组中所有其他元素的相对位置将保持不变。那就是对于在ai + 1之后的所有元素，它们仍将在ai + 1之后，对于在ai前的所有元素，它们仍将在ai之前。这也意味着，如果ai或ai + 1与元素aj形成一个反转，那么它们在交换之后仍将与其形成一个反转。因此，如果我们交换ai和ai + 1，将仅影响这两个元素过去形成的反转。由于两个要素可能参与不止一个反演，因此我们也证明了引理。
引理3:我们至少需要执行相邻元素的NI交换才能对数组进行排序，其中NI是数组中反转的数量
证明:在排序数组中没有反转。同样根据引理2，单个交换最多可以减少一次反转。因此，我们至少需要执行与反转次数一样多的交换。
引理4:我们总是可以对执行相邻元素的NI交换的数组进行排序，就像在NI上方一样，该数组中的反转数也是如此。
证明:如果我们假设数组中不存在两个相邻元素的求逆，则根据引理1，将对数组进行排序并完成。
否则，至少有一对相邻的元素构成一个反演。我们可以交换它们，从而将反演的总数减少一次。我们可以继续准确执行NI次此操作。
现在，我已经从答案的开头证明了我的观点。
剩下的唯一问题是如何计算给定数组中的反转次数。您可以使用对合并排序的略微修改来做到这一点，在合并阶段中累积反转。您可以查看this answer以获得有关如何实现该功能的详细信息。该算法的总体复杂度为O(n*log(n))。
关于algorithm - 通过使用最小交换来交换相邻元素来对序列进行排序，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20990127/