首页 > 代码库 > July收集荷兰国旗问题之三路partition
July收集荷兰国旗问题之三路partition
这道题目和分成两块的partition的扩展,例如有一堆0 1 2 数字组成的数组,要分成 00 00 11 1 1 222 2这种顺序的。
利用lumoto版的partition可以很好的解决,比hoare好多了,而且直接利用loop invariant,变成i j k三个指针,[low,i]=0 [i+1,j]=1, [j+1,k-1]=2, 里面如果新来2的话,直接k++,
如果是1的话,需要和a[j+1] swap, 同时j++, 如果0的话,需要先和a[i+1] swap i++, 然后和 a[j+1] swap j++, 因此算法如下:
void NertherlandFlags(int *a, int n) { int low=0,high=n-1; int i=low-1,j=low-1; for(int k=low;k<=high;k++) { if(a[k]==2) ; else if(a[k]==1) { j++; swap(a[j],a[k]); } else if(a[k]==0) { i++; swap(a[i],a[k]); j++; swap(a[j],a[k]); } } }代码比较好写,感觉这都是一类题,
1.快排的partition,注意留一个pivot,算导是留最后一个,所以loop到high-1就停了,里面和pivot比,最后加一次swap把pivot放中间
loop invariant: [low,i] <pivot, [i+1, j-1]>pivot, =放那边都行,exit loop时 j=high, 最后把swap跳进来
2.奇偶排序,整个区间划分为左奇右偶,和%2=0 =1比,loop 到high,
loop invariant: [low,i] 奇, [i+1, j-1]偶, exit时 j=high+1, 包含整个区间了
3.荷兰国企问题,整个区间划分为0 1 2 (红 黄 蓝三块), loop 到high,
loop invariant: [low,i] 0, [i+1, j] 1, [j+1, k-1] exit时 j=high+1, 包含整个区间了
July收集荷兰国旗问题之三路partition
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。