首页 > 代码库 > 基于快排思想的题目(一)——荷兰旗问题

基于快排思想的题目(一)——荷兰旗问题

基于快排思想的题目(一)——荷兰旗问题


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


1. 题目描述


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



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不要动,因为交换之后的数值我们还不知道情况呢,我们需要进一步判断。


移动的图示如下:






代码如下:

#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; 
}







基于快排思想的题目(一)——荷兰旗问题