荷兰国旗问题
荷兰国旗问题
荷兰国旗是由红白蓝3种颜色的条纹拼接而成,如下图所示:
如果这样的条纹有多个,但是仍由这3种颜色组成,且各种颜色数量不一,并且随机组成了一个新的图形,新的图形的情况之一如下图所示:
现在给定一个包含红色、白色和蓝色,一共n个小球,原地对它们进行排序,使得小球按照红色、白色、蓝色顺序排列。这里我们用0、1、2分别代表红白蓝三种颜色。
这其实是快速排序的另一种解决问题的方法。
我们可以将整个数组分成三段,分别为0,1,2,那么我们怎么实现呢?我们定义三个指针,l=-1,r=n,cur=0;l指向最后一个为0的元素,r为第一个为2的元素,cur指针指向当前元素,我们整个数组的循环条件是cur< r (如果是l< r会造成死循环)。
如果cur指向元素等于1,cur指针后移即可,如果等于0,交换a[cur]和a[l]的后一个元素相当于我们把a[cur]放到l+1位置,然后cur指针后移;如果cur指向元素等于2,交换[cur]和a[r]的前一个元素相当于我们把a[cur]放到r-1位置,这里要注意的是,我们cur指针不能后移,因为此时cur位置的元素还没有被检查,是之前r-1位置的元素。这样就可以将元素排好序。
附代码:
1 |
|