# 1. 两类数据划分
## 1.1 问题描述
给定一个数组和一个数字`num`，把数组中小于`num`的数字放在数组的左边，大于`num`的数字放在数组的右边。要求额外空间复杂度为`O(1)`，时间复杂度为`O(n)`。
## 1.2 问题分析
对于这个问题，最直观的做法就是采用类似快排的思路，定义两个指针`i`和`j`。比如下面的图示：
<img src='http://weizu_cool.gitee.io/gif-source/images/屏幕截图 2022-01-04 101629.png' />
对应代码：
~~~
/**
* 一次划分结果，处理两类划分问题
* 即：默认数组中不存在等于num的元素
* @param arr 待划分数组
* @param num 划分边界
*/
public void partition(int[] arr, int num){
int left = 0, right = arr.length - 1;
while(left <= right){
while(arr[left] < num) left++;
while(arr[right] > num) right--;
if(left <= right) swap(arr, left, right);
}
}
/**
* 异或运算进行交换两个数字
* @param arr 数组
* @param left 左边下标
* @param right 右边下标
*/
private void swap(int[] arr, int left, int right) {
int temp = arr[left] ^ arr[right];
arr[left] = temp ^ arr[left];
arr[right] = arr[left] ^ temp;
}
~~~
以`arr=[1, 6, 3, 2, 5, 1, 7, 2, 10]`，`num=4`为案例，运行结果：
<img src="http://weizu_cool.gitee.io/gif-source/images/屏幕截图 2022-01-04 104836.png"/>
那么根据上面的思路，我们可以规定左边的部分为严格小于`num`的部分，对于其后的元素我们使用扫描加交换的方式可以简化一下这个算法过程，如下图所示：
<img src='http://weizu_cool.gitee.io/gif-source/images/屏幕截图 2022-01-04 103042.png' />
对应代码：
~~~
/**
* 一次划分结果，处理两类划分问题
* 即：默认数组中不存在等于num的元素
* @param arr 待划分数组
* @param num 划分边界
*/
public void partition(int[] arr, int num){
int i = -1;
for (int j = 0; j < arr.length; j++) {
if(arr[j] > num) continue;
swap(arr, i + 1, j);
i++;
}
}
/**
* 异或运算进行交换两个数字
* @param arr 数组
* @param left 左边下标
* @param right 右边下标
*/
private void swap(int[] arr, int left, int right) {
int temp = arr[left] ^ arr[right];
arr[left] = temp ^ arr[left];
arr[right] = arr[left] ^ temp;
}
~~~
以`arr=[1, 6, 3, 2, 5, 1, 7, 2, 10]`，`num=4`为案例，运行结果：
<img src='http://weizu_cool.gitee.io/gif-source/images/屏幕截图 2022-01-04 104642.png'/>
# 2. 三类数据划分
注意到在上面的两类数据的划分中没有考虑等于问题，而这个问题是比可避免的。所以这里我们需要继续优化这个问题。
类似的，这里还是先考虑快排的一次划分，这里摘抄一下快排的一次排序：
~~~
/**
* 按照左边第一个数作为轴值进行比较划分
* @param arr 待排序数组
* @param left 左边界
* @param right 右边界
* @return 轴值的最终有序位置
*/
private int partition(int[] arr, int left, int right) {
int value = arr[left];
while (left < right) {
while (left < right && arr[right] >= value) {
right--;
}
swap(arr, right, left);
while (left < right && arr[left] <= value) {
left++;
}
swap(arr, right, left);
}
return left;
}
~~~
以案例`arr=[4, 6, 3, 2, 5, 4, 1, 7, 4, 10, 4]`为例，然后打印一下每次划分的结果：
<img src='http://weizu_cool.gitee.io/gif-source/images/屏幕截图 2022-01-04 112202.png'/>
这里可以发现，在快排中，存在相同元素的`num`即使作为轴值，也不会达到相同的`num`值放置在中间一堆。而是在不断的递归子问题划分中不断有序。所以如果要做到三部分数据的有序，我们需要确保有严格的数据界限逻辑划分，类似于上面的第二种解法，如下图所示：
<img src="http://weizu_cool.gitee.io/gif-source/images/屏幕截图 2022-01-04 154000.png"/>
对应代码如下：
~~~
/**
* 划分数组数据为三部分
* @param arr 待划分数组
* @param num 划分值
*/
private void partitionWithThreePart(int[] arr, int num) {
int i = 0, j = arr.length - 1, k = 0;
while(k <= j){
if(arr[k] < num) { // 小于num的情况
swap(arr, i, k);
if(i == k) k++;
i++;
}else if(arr[k] > num){ // 大于num的情况
swap(arr, k, j);
j--;
} else{ // 等于num的情况
k++;
}
}
}
/**
* 异或运算进行交换两个数字
* @param arr 数组
* @param left 左边下标
* @param right 右边下标
*/
private void swap(int[] arr, int left, int right) {
int temp = arr[left] ^ arr[right];
arr[left] = temp ^ arr[left];
arr[right] = arr[left] ^ temp;
}
~~~
