HappyCpp

一个不会打代码的程序猿

0%

荷兰国旗问题

发表于 更新于 分类于 阅读次数： 评论数：

荷兰国旗问题

荷兰国旗问题

荷兰国旗是由红白蓝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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<stdio.h>
#include<algorithm>
using namespace std;
int a[105];
int main() {
	int n;
	scanf("%d",&n);
	for(int i=0; i<n; i++) {
		scanf("%d",&a[i]);
	}
	int l=-1,r=n,cur=0;
	while(cur<r) {
		if(a[cur]==1)
			cur++;
		else if(a[cur]==0) {
			swap(a[cur],a[++l]);
			cur++;
		} else if(a[cur]==2)
			swap(a[cur],a[--r]);
	}
	for(int i=0; i<n; i++) {
		printf("%d ",a[i]);
	}
	printf("\n");
	return 0;
}

附题目链接：https://leetcode-cn.com/problems/sort-colors/