三色旗专题

Algorithm Gossip:三色旗问题

【问题】假设有一条绳子,上面有红白蓝三种颜色的旗子,开始时旗子的颜色并没有顺序,现将其分类,排成蓝白红的顺序,每次只能调换两个旗子,问怎样移动次数最少? 【算法分析】排列顺序是b、w、r,定义三个指针: 1、b永远指向第一个不是b的元素; 2、w是遍历的指针,向前移动,并判断指向元素,如果指向w则继续前进,如果指向b则与b指向的元素交换,b、w各向前方移动一位,,如果是r则与r指向的元素交