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

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

这是一个经典的算法问题。如果交换的最小数量等于数组中的反转数量。如果我们的索引i和索引j使得a i > a j且i
<j，则这称为反转。让我们证明这一说法！在此过程中，我将需要一些引理：

引理1： 如果没有两个 相邻 元素的求逆，则对数组进行排序。
证明： 让我们假设没有两个相邻的元素构成一个反转。这意味着在区间[0，n-1]中，所有i 的i <= i i +
1。作为

<=

可传递的，这意味着将对数组进行排序。

引理2： 两个相邻元素的一次交换最多会将数组中的反转总数减少1。
证明： 当我们交换两个相邻元素a i和i + 1时，它们相对于所有其他元素的相对位置在数组中将保持不变。也就是说，对于所有在i +
1之后的元素，它们仍将在i + 1之后，对于在i之前的所有元素，它们仍将在a i之前。这也意味着，如果一个i或一个i + 1与一个元素a
j形成一个倒数，那么它们在交换之后仍将与其形成一个倒数。因此，如果我们交换一个i和i +
1我们将仅影响这两个元素形成的反转。由于两个元素可能参与的反演次数不超过一个，因此我们也证明了引理。

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

引理4： 我们总是可以对执行相邻元素的NI交换的数组进行排序，就像在NI上方一样，数组中的反转次数也是如此。
证明： 如果我们假设数组中不存在两个相邻元素的求逆，则根据引理1，将对数组进行排序并完成。
否则，至少有一对相邻的元素构成一个反演。我们可以交换它们，从而将反演的总数减少一次。我们可以继续准确执行NI次此 *** 作。

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

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

O(n*log(n))

。