lintcode 625 数组划分

/**
 * 将一个没有经过排序的整数数组划分为 3 部分:
 * 1.第一部分中所有的值都 < low
 * 2.第二部分中所有的值都 >= low并且 <= high
 * 3.第三部分中所有的值都 > high
 * 返回任意一种可能的情况。
 *输入:
 * [4,3,4,1,2,3,1,2]
 * 2
 * 3
 * 输出:
 * [1,1,2,3,2,3,4,4]
 * 解释:
 * [1,1,2,2,3,3,4,4] 也对, 但 [1,2,1,2,3,3,4,4] 不对
 * 
 */
public class Test {

    public static void main(String[] args) {
        int nums[] = new int[]{4,3,4,1,2,3,1,2};
        partition2(nums,2,3);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }

    public static void partition2(int[] nums, int low, int high) {
        if(nums==null || nums.length==0){
            return ;
        }
        int left = 0;//前面的数组指针 已经排序到哪
        int right = nums.length-1;
        int index = 0;// 遍历下标
        while(index <= right){
            if(nums[index]<low){
                if(index!=left){
                    int temp = nums[index];
                    nums[index] = nums[left];
                    nums[left] = temp;

                }
                left++;
                index++;
            }else if(nums[index]>high){
                // 大于的直接放后面
                if(index!=right){
                    int temp = nums[index];
                    nums[index] = nums[right];
                    nums[right] = temp;

                }
                right--;
            }else{
                index++;//遍历下标自增，后面如果发现有小于low 会直接交换 left数据，所以没事
            }
        }
    }
}