c++ - 置换成本

Question

我得到集合 {1,2,...,n} 的排列。我必须仅通过以最低总成本交换位于连续位置的数字来对这种排列进行排序。交换位于连续位置的元素 x,y 的成本是 min(x,y)。

例如，如果我有 3,1,2,4 的排列，则总最小成本为 3。因为我执行了这些步骤（（x,y）意味着将 x 与 y 交换）：

• (3,1),2,4 结果 1,3,2,4 成本 min(1,3)=1
• 1,(3,2),4 结果 1,2,3,4 成本 min(2,3)=2

总成本为 3。

我尝试了蛮力，通过交换最小成本未排序对，直到没有未排序对，但这种方法显然不够快。

我的问题是，在给定条件的情况下，如何找到最低的排序成本？

Answer 1

对序列进行排序的连续数字交换的数量等于倒序的对数。

例如

6 1 3 2 4 5

下面列出了以相反顺序排列的对：

(6,1) (6,3) (6,2) (6,4) (6,5) (3,2)

所以

对序列进行排序的操作是：

swap(6,1) 1 6 3 2 4 5
swap(6,3) 1 3 6 2 4 5
swap(6,2) 1 3 2 6 4 5
swap(6,4) 1 3 2 4 6 5
swap(6,5) 1 3 2 4 5 6
swap(3,2) 1 2 3 4 5 6

所以操作是确定的（除非你做了一些无用的操作）。

您只需要以相反的顺序计算所有对（x，y），并总结min（x，y）。

Answer 2

这种算法听起来像插入排序。插入排序基于消除排列中的反转。你的任务是消除插入排序中的倒置。如您所知，排序数组没有任何反转。

插入排序算法的时间复杂度是 O(n+d)，其中 n 是元素的数量，d - 是反转的数量。

排列中的最大反转次数为 n*(n-1)/2，最小值为 0。

您可以使用修改后的归并排序在 O(n*lg n) 中查找数组中的反转数。