按条件重组数组

快速排序变种：

一、将数组按条件重组成两半

重点：分割数组 + 扩展条件封装
数组分割：两种方式
1. 两个游标一个从前向后，一个从后向前
2. 两个游标都是从前向后。
时间复杂度：两种时间复杂度都是O(n)

条件封装–条件包括：
1. 按奇数偶数分割
2. 按正数负数分割
3. 按整除3不整除3分割
4. ……

eg. 剑指offer14—调整数组顺序使奇数位于偶数前面

private static void swap(int[] arr, int i, int j) {
    if(i == j) return;
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}
private boolean Condition(int a){
    return a&1==0?true:false;
    //return a>0?true:false;
    //return a%3==0?true:false;
}
/*单方向走*/
public void sortByCondition(int[] arr){
    int i = -1;//i为奇数偶数分割点，实际上是前一半的最后一个数字。
    for(int j = 0; j < arr.length; j++)
        if(j > i && !Condition(arr[j])) swap(arr, ++i, j); //判断尽量相等的不要交换
}
/*双向往中间走*/
public void sortByConditionII(int[] arr){
    int i = 0, j = arr.length-1;
    while(i < j){
        while(i < j && Condition(arr[j])) j--;
        while(i < j && !Condition(arr[i])) i++;
        if(i < j) swap(arr, i, j);//判断尽量相等的不要交换
    }
}

---

二、将数组按条件重组成三半

LeetCode75 SortColors
对于元素取值有限的数组【此题数组中包含0，1，2】，只遍历一遍 https://leetcode.com/problems/sort-colors/

——将数组分成三半
想法是若将数组分成两半，维护一个边界即可。若将数组分成三半，要维护两个边界：第一半的右边界，第三半的左边界

public void sortColors(int[] arr){
    int i = -1, j = arr.length, p = 0;
    while(p < j){
        if(p > i && arr[p] == 0) swap(arr, ++i, p);//注意此处判断相等的不可以交换了，否则p不向前走了
        else if(p < j && arr[p] == 2) swap(arr, --j, p);
        else p++;
    }
}

---

三、扩展

若要求将数组分成四半、五半或者更多。就要维护更多的边界，避免混乱，都从前面向后走。
【采用平移插入，就是根据下一个值该插入哪个范围中，就将该范围加了1个后将其后面所有范围都要增加1个数，就达到了在该范围内插入一个的效果】

eg. 还以sortColors为例

public void sortColors(int[] arr){
    int b0 = -1, b1= -1, b2 = -1;
    for(int i = 0; i < arr.length; i++){
        switch (arr[i]){
            case 0:
                arr[++b2] = 2;
                arr[++b1] = 1;
                arr[++b0] = 0;
                break;
            case 1:
                arr[++b2] = 2;
                arr[++b1] = 1;
                break;
            case 2:
                arr[++b2] = 2;
                break;
        }
    }
}

若是多个范围就增加border数量，以及判断的case数量即可。