首页 > 代码库 > 基于快排思想的题目(一)——荷兰旗问题
基于快排思想的题目(一)——荷兰旗问题
基于快排思想的题目(一)——荷兰旗问题
快排的实现大家估计都知道,主要就是一个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; }
基于快排思想的题目(一)——荷兰旗问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。