荷兰国旗
荷兰国旗问题：简单来说就是，我们以一个数num作为基准，将一个数组划分为左侧为小于num的部分，右侧为大于num的部分，中间为等于num的部分。
假设一个数组为4 3 7 6 5 2 5，且num=5，以此来划分，最终数组被划分为左侧小于5，中间等于5，右侧大于5。像这样：4 3 2 5 5 6 7 。需要注意的是经过这样划分后的数组不一定是有序的。
如何划分
假设我们需要对L 到 R 的序列区间变成满足荷兰国旗描述的序列区间，我们需要先准备 less 指针和 more 指针分别指向 L 的左侧和 R 的右侧。cur指针指向 L 。less 指向的区域为小于 num的区域， more 指向的区域为大于 num 的区域。如下图示：
图片1.png
从 cur 当前指向的位置开始，将其指向的数与 num (num = 5) 进行比较。如果该数小于 num ，则 cur 指向的数就与 less 区域的后一个数比较，并且less指针加一，cur 指向下一个数；如果该数等于 num， 则 cur 指针直接指向下一个位置；如果该数大于 num ，则 cur 指向的数就与 more 区域的前一个数比较，并且 more 指针减一。一直重复这样的划分操作指导 cur 指针与 more 相遇为止。
图片2.png
伪代码描述
while(cur < more){
if(当前数 = num) cur++
if(当前数 < num) 和小于区域后一个数交换，less++,cur++
if(当前是 > num) 和大于区域前一个数交换，more--
}
完整代码
public static int[] partition(int[] arr,int left,int right,int num) {
//if(arr == null) return null;
int less = left - 1;
int more = right + 1;
int current = left;
while(current < more) {
if(arr[current] < num) {
swap(arr,less+1,current);
less++;
current++;
}else if(arr[current] > num) {
swap(arr,more-1,current);
more--;
}else {
current++;
}
}
return new int[] {less+1,more};
}
private static void swap(int[] arr,int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
