日期:2014-05-20  浏览次数:20711 次

步长最短排序算法
一个随机数组 arr=[0,0,2,1,3,2]
排序中你只能用一个方法
swap(index1,index2)
要求按从大到小排序
结果是 [3,2,2,1,0,0]

要求执行swap函数次数最少

------解决方案--------------------
0 0 2 1 3 2
3 x 1
2 x 1 1
2 x1 1
1 x1
0 1 1 x
0 1 1 x
表头(第一行)是原始数据
表的Y轴(第一列)是排序后的预期结果
表格单元内容:x表示目标位置,1表示初始的位置与目标位置对照,需要移动的单元
现在问题就变成了,把1对应的位置移动到本行x对应的位置,要求移动次数最少。

首先,已经在位置上的单元 (x1)不用移动。(不用移动的,将其相关标记清除之)
其次,只有一个位置需要移动的,先移动 (当然,每次移动了,记得更新当前表格)
然后,剩下的有些一行有多个位置可以移动(例如2这个数字),如果不满足以上两个条件,找对称位置(即看单元[i,j]=1时,是不是有[j,i]也有1)的做交换
最后剩下的,依次移动到对应位置就好了,没什么区别。

楼主给的例子运行过程比较特殊:
首先,【3,3】,【4,4】是x1,不用移动。 清除标记,结果为
0 0 2 1 3 2
3 x 1
2 x 1
2 x
1 x
0 1 1 x
0 1 1 x
其次,第一行【1,5】只有一个需要移动,所以调用 swap(5,1) (我是以1为起始)
然后,第二行也只有一个要移动,移动之,调整标记,全部完成了。