PASCAL 排序问题
发布网友
发布时间：2022-04-30 01:54
共1个回答
热心网友
时间：2022-06-28 12:50
看到最少排序交换次数的题目,应该马上想到用"置换群"O(n)出解.
置换群的话简单介绍下,就是:
比如说你的输入中有
1 3 5 4 2(假设它叫做a数组)
那么把它排序得到
1 2 3 4 5(假设叫b)
那么我们看到(先看完,别问为什么),
位置为1的1要到1位置,1->1,不用交换
位置为2的3要到3位置,可是a数组中3位置为5,5要到b中的5位置,可是a中5位置为2,2要到2位置,2位置是3,那么我们可以得到3->5->2->3,交换2次(也就是置换群的长度减2)
4位置不变4->4,不用交换
可以证明这样得到的交换次数一定是最少的.
莫诺原创.如有疑问请在
http://grayluck.blog.163.com留言.
