【笔记】两种交换元素的方案对比

交换元素,使序列有序,求最少交换次数

 

第一种是只能交换"相邻”元素,使序列有序,求最小交换次数,

假如是是序列升序,只需要求逆序对数。

3 2 1-> 1 2 3 

3次

4 2 3 1 -> 1 2 3 4

2 3 1 4 (3)

2 1 3 4 (1)

1 2 3 4 (1)

正好对应每个数,和他右边数的逆序对个数

 

第二种是可以交换任意两个位置的元素,使之有序,求最小交换次数,

答案是: n-交换数字形成的环(置换环)的个数。

(就是所有环中数据各自交换,的次数和)(sz和 - sz数)

比如 {5 1 3 2 4 7 6 8 } , 求将这个序列变成升序序列的最小交换次数,

那么这个序列中的环有{ 5,1,2,4},{7,6},{3},{8}, 那么最小交换次数就是 8-4,

 

求降序的最小交换次数,只需要将序列逆置,再进行求解 。

原文地址:https://www.cnblogs.com/xwww666666/p/11869659.html