基于快排思想的题目（一）——荷兰旗问题

客官°小女子只卖身不卖艺 2022-08-06 01:08 148阅读 0赞

**基于快排思想的题目（一）——荷兰旗问题**

快排的实现大家估计都知道，主要就是一个partition和交换的过程。这个思想其实是很巧妙的，基于此，很多题目都可以用它来很好地解决。这篇我们讲到了注明的荷兰旗问题，就是可以用到快排的思想~后续还有一系列的题目，应该都是可以用到快排思想的，后面慢慢整理ing~

# 1. 题目描述 #

这个题目是由荷兰科学家Dijkstra提出来的，首先输入乱序排列的三色小球（红，白，蓝），如果通过两两交换，使得所有红色小球排在前面，白色小球排在中间，蓝色小球排在最后~

![Center][]

# 2. 图文并茂来解答 #

使用快排的思想，我们先用3个指针head, middle, tail。初始时，head和middle指向第一个球，tail指向最后一个球。然后移动和交换的规则如下：

（0表示红，1表示白，2表示蓝）

*  middle指针所指元素为0时，与head指针所指的元素交换，而后middle\++，head\++ ；
 *  middle指针所指元素为1时，不做任何交换（即球不动），而后middle\++ ；
 *  middle指针所指元素为2时，与tail指针所指的元素交换，而后，middle指针不动，tail\-- 。

直到current>tail, 停止移动。

其实我们可以理解到：当middle指向0的时候，这个0应该是在前面的，所以说我们需要把它和head交换，交换之后自然head++，middle++，因为此时已经保证了head前面的都是0了；后面当middle指向2的时候，和上面原因一样，我们需要和tail交换，交换了之后只要把tail--，当时middle不要动，因为交换之后的数值我们还不知道情况呢，我们需要进一步判断。

移动的图示如下：

![Center 1][]

![Center 2][]

代码如下：

#include<iostream>
    using namespace std; 
    
    void DutchFlag(int *a, int head, int middle, int tail)
    {
    	while(middle<=tail)
    	{
    		if(a[middle]==0)
    		{
    			swap(a[middle], a[head]); 
    			head++, middle++; 
    		}
    
    		if(a[middle]==1)
    			middle++; 
    
    		if(a[middle]==2)
    		{
    			swap(a[middle], a[tail]); 
    			tail--; 
    		}
    	}
    }
    
    int main()
    {
    	int a[10]={0, 1, 2, 1, 1, 2, 0, 2, 1, 0}; 
    	int num=10; 
    
    	for(int i=0; i<num; i++)
    		cout<<a[i]<<' '; 
    	cout<<endl; 
    
    	int head=0; 
    	int middle=0; 
    	int tail=num-1; 
    	
    	DutchFlag(a, head, middle, tail); 
    
    	for(int j=0; j<num; j++)
    		cout<<a[j]<<' '; 
    
    	return 0; 
    }

[Center]: /images/20220806/b670f4368ded47e4b6f66c95123e3816.png
[Center 1]: /images/20220806/f7c1631cafff43ecb594b6b1790f7088.png
[Center 2]: /images/20220806/4a9489341d2f46a7aa25fdb41bb9f9cf.png