企业网站用什么cms比较好,北京网站建设制作开发,深圳服务平台网站,网站建设 需要ae吗在使用partition-exchange排序算法时#xff0c;如快速排序算法#xff0c;我们会遇到一些问题#xff0c;比如重复元素太多#xff0c;降低了效率#xff0c;在每次递归中#xff0c;左边部分是空的(没有元素比关键元素小)#xff0c;而右边部分只能一个一个递减移动。…在使用partition-exchange排序算法时如快速排序算法我们会遇到一些问题比如重复元素太多降低了效率在每次递归中左边部分是空的(没有元素比关键元素小)而右边部分只能一个一个递减移动。结果导致耗费了二次方时间来排序相等元素。这时我们可以多分一个区即小于区等于区大于区。传统快排为小于区和大于区 下面我们通过一个经典例题来练习这种思想。
荷兰国旗问题
”荷兰国旗难题“是计算机科学中的一个程序难题它是由Edsger Dijkstra提出的。荷兰国旗是由红、白、蓝三色组成的。 现在有若干个红、白、蓝三种颜色的球随机排列成一条直线。现在我们的任务是把这些球按照红、白、蓝排序。
样例输入
3
BBRRWBWRRR
RRRWWRWRB
RBRW
样例输出
RRRRRWWBBB
RRRRRWWWB
RRWB
思路
现在我们的思路就是把未排序时前部和后部分别排在数组的前面和后面那么中部自然就排好了。
设置两个标志位head指向数组开头tail指向数组末尾now从头开始遍历
(1)如果遍历到的位置为1那么它一定是属于前部于是就和head交换值然后headnow
(2)如果遍历到的位置为2说明属于中部now
(3)如果遍历到的位置为3说明属于后部于是就和tail交换值然而如果此时交换后now指向的值属于前部那么就执行(1)tail--
废话不多说上代码。
#includeiostream
#includealgorithm
using namespace std;const int maxn 100 5;int n;
string str;
int main(){cinn;while(n--){cinstr;int lenstr.size();int now0,ans0;int head0,taillen-1;while(nowtail){if(str[now]R){swap(str[head],str[now]);head;now;}else if(str[now]W){now;}else{swap(str[now],str[tail]);tail--;}}coutstrendl;}return 0;
}其实只要解题的话统计三个数量就好了但是分三区的思想一定要有。
快排分三区以后降低了递归规模避免了最差情况性能得到改进。
