荷兰国旗问题

package Test01;
/*
 * （荷兰国旗问题）
 * 给定一个数组arr，和一个数num，请把小于num的数放在数组的 左边，等于num的数放在数组的中间，大于num的数放在数组的 右边。
 * 要求额外空间复杂度O(1)，时间复杂度O(N)
 */

public class NtherlandsFlag {

	public static void main(String[] args) {
		int[] arr = { 1, 3, 2, 9, 8, 7, 1, 0, 7, 3, 3, 4, 5, 3 }; // 要排序的数组

		int[] test = partition(arr, 0, arr.length - 1, 7); // L,左边界，R，右边界，P，给定的num大小

		for (int i = 0; i < arr.length; i++) { // 打印
			System.out.print(arr[i] + "  ");
		}
		System.out.println("
" + test[0] + "  " + test[1]); //打印等于num的开始和结束下标
	}

	public static int[] partition(int arr[], int L, int R, int num) {
		int less = L - 1;
		int more = R + 1;
		while (L < more) {
			if (arr[L] < num) {                            //一定要是else if
				swap(arr, L++, ++less);
			}

			else if (arr[L] > num) {
				swap(arr, L, --more);
			} else {
				L++;
			}

		}
		return new int[] { less + 1, more - 1 };

	}

	public static void swap(int[] arr,int a,int b) {           //交换
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}

}