奥运国旗

发表于   |   分类于   |  

昨天中国的女排姑娘们以3：1击败了荷兰队，比赛荡气回肠，相当激烈，中国姑娘们在不被看好的情况下，硬是靠自己的拼搏杀出一条血路！
2

你有没有发现，很多国家的国旗，都是三种颜色的条纹旗，而荷兰、俄罗斯、法国的国旗，甚至连颜色都一样，实在是很难区分。
1

好了，话不多说，我们来看下今天的问题，与三色旗有关。

快排一次的应用

将数组中的大小写字母分开

大写字母放后面，小写放前面。
这个很简单，一头一尾指针，遇到不合适的就交换。

1
2
3
4
5
6
7
8
9
void partitation(char A[], int low,int high)
{
	while(low<high)
	{
		while(low<high&&isUpper(A[high])) --high;
		while(low<high&&isLower(A[low])) --low;
		swap(A[low],A[high]);
	}
}

将数组中的0元素放到后面，非零元素的相对位置不变

相比于上一题，这题要求非零元素的相对位置不变

这题还是设置2个指针，都是放在尾部。
指针p判断是否是0，而指针q指向要交换的位置，一般为尾部最后一个0的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void partation(int A[],int low, int high)
{
	int p=high;
	int q=high;
	while(p>=low)
	{
		if(A[p]!=0)//每当遇到一个需要交换的p的时候
		{
			swap(A[p],A[q]);
			q--;
		}
		p--;
	}
}

荷兰国旗

数组中有三种类型的数据，把第一种的类型的全部放左边，第二种类型的全部放中间，第三种类型的全部放后面。
如，数组中有0，1，2三种数字，
0121120210
变为=>
0001111222

步骤

设置三个指针： 一前 begin，一后 end, 一现在指向的current
current从头往后遍历

  • current指0时，与begin交换，current++，begin++；
  • current指1时，current++；
  • current指2时，与end交换，end–，current不动(换来了一个新的)
    3
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    while(current<=end)
    {
    	if(A[current]==0)
    	{
    		swap(A[begin],A[end]);
    		current++;
    		begin++;
    	}
    	else if(A[current]==1)
    	{
    		current++;
    	}
    	else
    	{
    		swap(A[current],A[end]);
    		end--;
    	}
    }