荷兰国旗问题

给定一个数组arr和一个数num,请把小于num的数放在数组的左边,等于num的数放在数组的中间,大于num的数放在数组的右边
要求:额外空间复杂度O(1),时间复杂度O(n)
开始设置两个指针,一个指向左边L-1处,一个指向右边R+1处,当前指针遍历整个数组。
1.当前值比给定值小的时候,左指针往右移动一格,然后和当前值交换,当前指针往右移动一格,因为左边的值始终是比给定值小的,所以不用再判断交换之后与给定值的大小。
2.当前值比给定值大的时候,右指针往左移动一格,然后和当前值交换,但是当前指针不移动,因为此时还不知道交换过后的值与给定值的大小。
3.当前值与给定值相等时,当前指针直接往右移动一格。

遍历结束即为荷兰国旗问题,荷兰国旗问题是快排partition的优化。

#include<cstdio>
int Less = 0;
int More = 0;
void swap(int arr[],int i,int j){
	int tmp = arr[i];
	 	arr[i] = arr[j];
		arr[j] = tmp;
} 
void NetherlandFlag(int arr[], int L, int R, int num){
	int less = L - 1;
	int more = R + 1;
	int cur  = L;
	while(cur < more){
		if(arr[cur] < num){
			swap(arr, cur++, ++less);
		}else if(arr[cur] > num){
			swap(arr, cur, --more);
		}else{
			cur++;
		}
	} 
		Less = less + 1;
		More = more - 1; 
}

int main(){
	int arr[]={13,12,22,55,12,5,12};
	NetherlandFlag(arr,0,6,12);
	for(int i=0;i<7;i++){
		printf("%d ",arr[i]);
	}
	return 0;
}