给定一个数组arr， 和一个数num， 请把小于等于num的数放在数
组的左边， 大于num的数放在数组的右边。
要求额外空间复杂度O(1)， 时间复杂度O(N)
问题二（荷兰国旗问题）
给定一个数组arr， 和一个数num， 请把小于num的数放在数组的
左边， 等于num的数放在数组的中间， 大于num的数放在数组的
右边。
要求额外空间复杂度O(1)， 时间复杂度O(N)
1 public class Code_08_NetherlandsFlag { 2 3 public static int[] partition(int[] arr, int l, int r, int p) { 4 int less = l - 1; 5 int more = r + 1; 6 // int index = L; //用index 遍历 7 while (l < more) { 8 if (arr[l] < p) { 9 swap(arr, ++less, l++); 10 } else if (arr[l] > p) { 11 swap(arr, --more, l); 12 } else { 13 l++; 14 } 15 } 16 return new int[] { less + 1, more - 1 }; 17 } 18 19 // for test 20 public static void swap(int[] arr, int i, int j) { 21 int tmp = arr[i]; 22 arr[i] = arr[j]; 23 arr[j] = tmp; 24 } 25 26 // for test 27 public static int[] generateArray() { 28 int[] arr = new int[10]; 29 for (int i = 0; i < arr.length; i++) { 30 arr[i] = (int) (Math.random() * 3); 31 } 32 return arr; 33 } 34 35 // for test 36 public static void printArray(int[] arr) { 37 if (arr == null) { 38 return; 39 } 40 for (int i = 0; i < arr.length; i++) { 41 System.out.print(arr[i] + " "); 42 } 43 System.out.println(); 44 } 45 46 public static void main(String[] args) { 47 int[] test = generateArray(); 48 49 printArray(test); 50 int[] res = partition(test, 0, test.length - 1, 1); 51 printArray(test); 52 System.out.println(res[0]); 53 System.out.println(res[1]); 54 55 } 56 }