问题描述：
给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。（要求额外空间复杂度O(1)，时间复杂度O(N)）
思路：
准备三个指针l、r、cur，l指向数组的第一个元素之前，代表小于num的区域，r指向数组最后一个元素之后，代表大于num的区域，cur为当前元素所在位置，遍历数组与num比较，小于num放左边，等于num放中间，大于num放右边。
具体流程：
一开始从数组第一个元素开始遍历，cur指针来到了4的位置，cur位置上元素与num比较，如下图所示：
如果当前元素小于num值，则将当前元素与小于num区域的下一个值交换，此时，4和4交换位置，当前元素后移一位，小于num区域扩大一个位置，即l++，如下图所示：
如果遇到大于num的数时，当前元素与r的前一位置元素交换位置，大于num的区域扩大一个位置，即r–，
继续比较，当前cur=9> 5,因此继续与r前一位置元素交换，r前移一个位置。
继续比较，5=5，大于num区域和小于num区域不变，即l和r不动，当前元素位置后移一位，即cur++，
这个时候，当前位置元素小于num，跟之前一样，当前位置元素与小于区域下一个元素交换，小于区域扩一个位置，l++，
以此类推，按照这种方法，最后将会把小于num的数放在左边，大于num的数放在右边，等于num的数则放在中间。
具体代码实现
public class NetherLandsFlag { public static int[] partition(int[]arr,int cur,int r,int num){ int l = cur-1; //这里多声明了一个变量，用来表示数组最后一个元素的下个位置 int more = r+1; while(cur<more){ if(arr[cur]<num){ //当前元素与小于区域的下一个元素交换，当前元素后移一位 swap(arr,++l,cur++); }else if(arr[cur]>num){ //当前元素与大于区域的前一个元素交换 swap(arr,cur,--more); }else{ //等于num的话，当前元素后移一位 cur++; } } //返回的是一个数组，l+1是小于区域的下个元素指针和more-1是大于区域的前一个元素指针， //也就是等于区域的第一个和最后一个元素指针，就是等于区域所有元素 return new int[]{l+1,more-1}; } //简单的两数交换 public static void swap(int[]arr,int i,int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }