我得到了元素的排列,{1, 2, 3, ..., N}我必须使用交换操作对其进行排序.交换元素x,y的操作具有成本min(x,y).
我需要找出排序排序的最低成本.我考虑过贪婪N,1并使用交换操作将每个元素放在它的位置,但这不是一个好主意.
如果您对数字 1, 2, ..., N进行排列，则排序后的集合将恰好是 1, 2, ..., N。所以你知道复杂度为 O(0) 的答案（即你根本不需要算法）。
如果你确实想通过重复交换对范围进行排序，可以重复“前进和循环”：在已经排序的范围（其中a[i] == i）上前进，然后交换a[i]，a[a[i]]直到完成循环。重复直到到达终点。这最多需要N − 1 次交换，并且它基本上执行排列的循环分解。