|
例:写一个算法,输入是一个二进制位的数组s,长度为n.该算法重新安排这个数组,让所有的0都在1的前面.
以下是伪代码:
sort_bits(s)
{
i=1
j=s.last
while(i<j)
{
while(i<j && s[i]==0)
i=i+1
while(i<j && s[j]==1)
j=j-1
// 上面的代码找到了左边第一个1和右边第一个0,接下来就交换这两个元素
// 程序开始时,这样操作合理!!!!
// 程序中间,这样的操作正常
// 程序即将结束时,i和j指向的元素是相邻着的
// 然后i变得和j一样,但是下一步由于i=j,此时j不会再变化
// 但是下面的swap仍会执行一次,所以程序仍然可以改进....
swap(s[i],s[j])
/*里面也设置i<j的判断的必要性:
不设置的话,一开始就有可能i递增并且指向了s.last,然后继续索引的话,造成错误
同理,j也同样必须设置
一般情况下,程序结束之前,i和j紧邻,而且指向的元素分别为0和1,不设置i<j的条件i仍可以正常变化
但是,此时j此时会指向原来的i,下一步的交换反而使结果不正确了.然后程序由于外面的i<j的限制会停止,但是结果不对了
以上两点是必须在中间也设置i<j的原因.
*/
}
}
总体来说,这个算法比较巧妙,基本只经过了一次遍历+交换元素的方法达到了目的,而且代码比较精炼,值得学习.
| 
转播
