场景:现有一个数组 其中 加号 + 和减号 - 混合,要求对数组重新排序,要求所有的加号都在减号前面
定义的一个可变数组 mArray
方法一.
基本上所有童鞋拿到这个问题后首先想到的是for循环,不可否认,我也一样,无论for循环中做什么判断都需要循环数组长度次 所以index的结果为数组长度
方法二.
打印结果 : 循环次数21次 也为数组的长度
解析:当startIndex 为 - 时,count - endIndex - 1 为+时,两者交换是有效交换
当startIndex 为 - 时,count-endIndex - 1也为 - 时 ,两者交换是无效交换,只会增加循环次数
那么究竟有没有能缩短循环次数的方法呢,答案是肯定的,当然有,只要将方法二的无效交换排除就可以了
方法三.
打印结果:index的循环次数是 12次
将方法二中 1.startIndex 为 + ,endIndex 为 - , startIndex ++ ,endIndex --
2.startIndex 为 +,endIndex 为 + ,startIndex ++,
3.startIndex 为 - ,endIndex 为 +,交换两者,然后startIndex ++ ,endIndex --,
4.startIndex 为 - ,endIndex 为 - ,endIndex ++
这样就完全避免了 再循环中的 无效交换,从而可以减少循环次数
不知道还有没有更好的方法,请各位童鞋多多指正~~~~